<分区>
这个函数的第 4 行平均运行多少？ O(logn) 或 O(n)
Minimum(A,n)
1. min= +inf
2. for i:1 to n
3. do if min>A[i]
4. then min=A[i]
<分区>
这个函数的第 4 行平均运行多少？ O(logn) 或 O(n)
Minimum(A,n)
1. min= +inf
2. for i:1 to n
3. do if min>A[i]
4. then min=A[i]
最佳答案
假设数组未排序(否则见下文):
它是 O(n) 因为:
您必须至少一次查看数组的每个条目，否则您没有查看的条目可能会更小
您必须最多查看一次每个条目，因为您永远不会忘记当前的最小值是多少。
数组是直接访问的(没有寻道时间)
如果数组已排序，则找到最小值只需取第一个条目，即 O(1)。但是，如果您只需要一次最小值(而不是重复获取和删除最小值)，则不值得对数组进行排序，因为排序需要 O(n*log(n))
关于algorithm - MINIMUM 函数第 4 行的平均运行时间是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28711487/