为什么 n^2 被认为是一种时间复杂度，而 n/2 不是？

Question

我搜索了整个堆栈溢出，但找不到一个简明的答案。考虑这段代码：

n = [ [1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12] ] # O(1)
for i in n: # O(n)
    for j in i: # O(n)
        print(j)

如果我对O()的理解是正确的，这个算法的时间复杂度是1+n*n，如果我们把无关紧要的1+丢掉，就变成了n^2 ，或二次时间。现在考虑这段代码：

n = input() # O(1)
for i in range(0, len(n), 2): # O(n/2)?
    print(n[i])

这次我们使用除法而不是指数：1+n/2 -> n/2。

但是我到处搜索，人们说 O(n/2) == O(n)，因为 O() 测量相对时间等。但是如果 O(n/2) 是绝对的，我们应该把它折叠成 O(n) 当使用 big O 时，这不会使像 log n 和 n! 这样的时间复杂度类型也不正确，因为它只意味着用绝对值修改 n...？

n^2 == n 因为它与 n/2 相同，但我们使用 ^ 而不是 /。 n! 是不正确的，因为阶乘只是一系列乘法，所以 n! 与 n*(n-1)*... 相同，我相信，在丢弃所有 - 1秒。 我哪里错了？

P.S。我对对数和大 O 符号的理解非常不完整，如果我遗漏了一些明显的东西，请不要恨我。

Answer 1

看看大O上的Wikipedia page

In typical usage the O notation is asymptotical, that is, it refers to very large x. In this setting, the contribution of the terms that grow "most quickly" will eventually make the other ones irrelevant. As a result, the following simplification rules can be applied:

If f(x) is a sum of several terms, if there is one with largest growth rate, it can be kept, and all others omitted.

If f(x) is a product of several factors, any constants (terms in the product that do not depend on x) can be omitted.

为什么 n^2 被认为是一种时间复杂度，而 n/2 不是？

Why is n^2 considered a type of time complexity but n/2 isn't?

python

algorithm

time-complexity

big-o