arrays - 内置函数的运行时间

Question

如果我使用 Java 的内置函数，我是否必须考虑运行时间，或者我应该将它们计为常数时间。以下函数的时间复杂度是多少

def int findMax(int [] a)
    {
    a.Arrays.sort();
    n=a.length;
    return a[n-1];
    }

Answer 1

这里几乎所有的工作都是由 sort() 算法完成的。对于数组排序，Java 使用 Quicksort，它具有 O(n log n) 平均值和 O(n^2) 最坏情况性能。

来自关于 sort() 的 Java 文档:

Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

鉴于您的问题缺少任何用例，以及您对我的回答的评论，我觉得我必须指出这是过早优化的典型示例。您正在寻找一个简单方法的数学复杂性，但没有任何迹象表明该方法将占您程序使用的 CPU 时间的任何重要部分。考虑到您的实现效率极低，这一点尤其正确:遍历数组并存储最高值的执行时间为 O(n)。