1

现在我正在尝试在 Python 函数中找到“基本步骤”。基本步骤是代码中的点，O(1)它本身就是复杂的。我很难在这个函数中找到它：

def mystery1(numbers): 
    n = len(numbers)
    total = 0
    i = 0
    while i < len(numbers):
        j = i
        while j < len(numbers):
            total += numbers[i]*numbers[j]
            j += 2
        numbers[i] = total
        i += 3

我想认为这里的基本步骤实际上是total += numbers[i]*numbers[j]因为它应该比函数中的任何其他语句执行更多次，但是我并不完全相信我有能力弄清楚它。任何帮助表示赞赏！

4

1 回答 1

0

O(1) 是算法的运行时间，它不依赖于输入的大小。

在你的情况下：

def mystery1(numbers): 
    n = len(numbers) # -> Likely O(1) since one simply needs to
                     # use log() to find the number of digits in a number.
    total = 0 # -> O(1) since you're simply assigning a value to memory.
    i = 0 # -> O(1) since you're simply assigning a value to memory.
    while i < len(numbers): # -> O(n) since the loop is dependent on n, 
                            # which is the length of numbers
        j = i # -> O(1) since you're simply assigning a value to memory.
        while j < len(numbers): # -> O(n) since the loop is dependent on n, 
                                # which is the length of numbers
            total += numbers[i]*numbers[j] # -> O(1) since you're simply 
                                           # adding two values from memory.
            j += 2 # -> O(1) since you're simply incrementing by 2
        numbers[i] = total # -> O(1) since you're simply assigning a value to memory.
        i += 3 # -> O(1) since you're simply assigning a value to memory.
于 2015-07-05T10:28:45.193 回答