python - 示例程序大o值

Question

我正在尝试了解编程逻辑的最坏情况，需要一些说明。

这是一个非常简单的程序，它需要一个数字 - 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。

Answer 1

好的，所以评论给出了一个非常明确的答案 - 但只是为了澄清(并正确回答问题):

这里定义大 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)，但只迭代字符串。