0 
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元素。它是伪代码。

4

7 回答 7

8

该算法的最佳情况和最坏情况的渐近运行时间没有区别。在所有情况下，您都必须遍历整个数组（n元素），您的算法将是 O(n)。

从理论上讲，您不可能在小于 O(n) 的时间内找到任意数组的最大元素，因为您应该始终至少访问每个元素一次。

于 2009-11-11T07:06:16.450 回答
4

该算法O(n)处于最佳情况、平均情况和最坏情况。它也不起作用，因为它只引用a1 和使用<它应该使用>的地方。

于 2009-11-11T07:07:22.120 回答
2

O(n) - 你必须扫描 n 个元素，或 n 个因子（n/2、n/4 等） - 仍然是 O(n)。

于 2009-11-11T07:05:32.753 回答
2

粗略地说，O(1) 意味着无论输入的大小如何，您都可以在固定数量的步骤中实现解决方案。

O(n) 意味着如果您有 n 个输入，则解决方案将在 An 步骤中实现（其中 A 是一个数字，而不是另一个变量）。显然，如果您有从 2 到 n 计数的 for 循环，即 n 个循环，这意味着如果您有 An 输入元素，您的循环将从 2 计数到 An，这意味着它与输入处于同一级别，所以这是O（n）。但这就是线性扫描的方式。:)

于 2009-11-11T07:17:15.663 回答
0

如果您的代码如下：

for i := 2 to n

那么该代码将是 O(n) 最好的情况。

我很好奇为什么你认为它可能是恒定的时间？

于 2009-11-11T07:11:44.147 回答
0

You have to traverse the whole array. So the complexity would be O(n).

于 2009-11-11T07:29:00.740 回答
-1

O(n)

you can achieve the O(1) if the array was sorted, so you'll just return the last element.

but in random arranged elements the best order for this problem is O(n)

于 2009-11-11T07:32:22.793 回答