f(n) = n O(n) 时间还是 O(1)？

Question

我知道通常你会在试图弄清楚给定算法的复杂程度时忽略系数，但是假设我在 for 循环中有一个变量 n：

[(n, n) for n in range(1,11)]

，其中 returns

[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9), (10, 10)]

这个赋值不就是一个复杂度O(1)的操作吗？我们不对 n 做任何操作。还是我误解了它的意思 - 也许 O(n) 时间描述了循环并完成所有这些分配需要多长时间？

上下文是下面的代码，是我为一个学校项目写的。

#Michael Frake, CMSC 350, UMGC, 5/22/2021

print("{:<7} {:<8} {:<8}".format('i','f(i)','g(i)'))
for i in range(21):
    print("-", end="")
print()
for i in range(1, 25, 1):
    f = (i / 2) + 10
    g = i
    print("{:<7} {:<8} {:<8}".format(i,f,g))
    if g > f:
        print("g overtook f when i was ", i)
        break

哪个returns

i       f(i)     g(i)    
---------------------
1       10.5     1       
2       11.0     2       
3       11.5     3       
4       12.0     4       
5       12.5     5       
6       13.0     6       
7       13.5     7       
8       14.0     8       
9       14.5     9       
10      15.0     10      
11      15.5     11      
12      16.0     12      
13      16.5     13      
14      17.0     14      
15      17.5     15      
16      18.0     16      
17      18.5     17      
18      19.0     18      
19      19.5     19      
20      20.0     20      
21      20.5     21      
g overtook f when i was  21

我试图查看这两个函数的时间复杂度是否存在差异。

Answer 1

我觉得你有点混淆了符号。 O 表示法中的 n 指的是输入元素的数量（或迭代次数 取决于 输入）。它与您如何命名变量没有任何关系。

所以应该是：

[(value, value) for value in range(1, n)]  # O(n)

其中 n 可以任意选择，因此 O(n) 中的这个简单的 for 循环运行s。如果它是恒定的，例如因为你总是运行正是你的情况下的 21 个元素，所以它只是 O(21) = O(1).

[(value, value) for value in range(1, 21)]. # O(21) = O(1)

如果我们这样做，情况就会改变：

elements = list()

for i in range(n):       # O(n)  -> Depending on "n" (number of inputs)
    for j in range(21):  # O(21) -> Constant
        elements.append((i, j))

这将表示为 O(n) * O(21)，这将简化为 O(n)，因为最坏时间复杂度取决于 n，输入元素的数量。

为了完整起见，以下将是 O(n²):

elements = list()

for i in range(n):       # O(n)
    for j in range(n):   # O(n) 
        elements.append((i, j))

f(n) = n O(n) 时间还是 O(1)？

Is f(n) = n O(n) time or O(1)?

python

big-o