如果一个算法调用另一个算法来执行它的功能，它的整体时间复杂度是否会受到影响？

Question

我正在尝试设计一个时间复杂度为 O(1) 的算法，该算法从不是最小值的数组中返回一个值。我知道搜索数组并比较其元素以找到最小的将使算法为 O(n)，因此不起作用。

如果我写一个单独的方法，使用排序算法先对数组进行排序，然后返回最小的，这会影响算法的时间复杂度吗？

这是我的代码：

private static int nonSmallestElement(int[] array) {

    int smallest = smallestElement(array);

    int index = (int) (array.length * Math.random());

    System.out.println("Index = " + index);

    for (int i = index; i < array.length; i++) {

        if (array[i] != smallest) {

            return array[i];

        }

    }

    return array[1];

}

private static int smallestElement(int[] array) {

    Arrays.sort(array);

    return array[0];

}

这里的Arrays.sort()方法是使用双枢轴快速排序算法，它是 O(n log(n))。现在这是否意味着该nonSmallestElement()方法也具有该时间复杂度，还是 O(1) 因为它不必处理排序？

Answer 1

你是对的，你需要计算所有动作来计算算法的复杂性。但是您应该了解规则，例如较大的包括较小的（更多示例）。在您的情况下，您调用smallestElement()一次 - O(nlogn) 而不是循环 O(n)。结果整体复杂度将是 O(n + nlogn)。但是最终的复杂度nonSmallestElement()是 O(nlogn) 因为 nlogn 更大。另一方面，不可能有比 O(n) 更好的算法来返回非最小值。因为您需要至少迭代所有元素一次才能找到最小值。异常可以是排序数组。从评论更新：这里有一个提示：如果您手头有两个不同的值，那么较大的值一定不是数组中的最小值。对于“典型”数组，您希望在任意两个元素中找到两个不同的值。@James K Polk