这个算法的复杂性是多少？

Question

procedure max (a[1..n]: integers)
    max := a[1]
    for i := 2 to n
        if max < a[i] then max := a[i]

是复杂性O(1)还是O(n)最佳情况？序列包含n元素.它是伪代码.

Answer 1

此算法的最佳情况和最差情况渐近运行时间之间没有区别.在所有情况下,您必须遍历整个数组(n元素),您的算法将是O(n).

从理论上讲,你无法在小于O(n)的范围内找到任意数组的最大元素,因为你应该总是至少访问一次每个元素.