我正在尝试了解编程逻辑的最坏情况,需要一些说明。
这是一个非常简单的程序,它需要一个数字 - 2938023,每个字符乘以一个随机数并填充到列表中。
填充列表后,我将获得最大值作为结果。
from random import randint
def test(A):
result = []
for each in str(A):
result.append(int(each)*randint(0,9))
return max(result)
print test(2938023)
此操作的最坏情况是什么?由于列表 - str(A) 仅迭代一次,我应该将其视为 log(n) 还是
我是否应该将其视为 n*n,因为列表将再次迭代以获得最大值。基于n的列表有2个pass。
最佳答案
好的,所以评论给出了一个非常明确的答案 - 但只是为了澄清(并正确回答问题):
这里定义大 O 的两个操作是:
for each in str(A):
- 这是一个O(n)
操作,它查看字符串中的每个字符 (A
).max(result)
- 这也是一个O(n)
,因为我们必须迭代整个列表来确定最大值(result
).
由于 len(A) == len(result)
我们可以称其为 2n
(与 nm
相对),并且因为它是big-O,我们舍弃常数因子,得到:O(n)
。
如果您想完全删除常数因子,您可以将函数重写为:
from random import randint
def test(A):
max_item = 0
for each in str(A):
new_item = int(each)*randint(0,9)
if new_item > max_item:
max_item = new_item
return max_item
这也是 O(n)
,但只迭代字符串。
关于python - 示例程序大o值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43928667/