10 + 9 + 8 + ... + 1 的时间复杂度是多少？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1597 天前的主题，其中的信息可能已经有所发展或是发生改变。

比如有一个两层的循环，如果是

n = 0  
for i in range(10):  
    for j in range(10):  
    n += 1  
    
print(n)  // 100

复杂度应该是 n^2 吧，那这样呢：

n = 0
for i in range(10):
	for j in range(i, 10):
		n += 1
            
print(n)   // 55

相当于 10 + 9 + 8 + ... + 1 = 55，这个复杂度应该怎么描述？

两个循环还好理解，如果是三层循环呢：

 n = 0
 	for i in range(10):
 		for j in range(i, 10):
 			for k in range(j, 10):
 				n += 1
            
 print(n)   // 220

主要是三层循环就想不明白了，求教这怎么理解呢？

range

for

循环

24 条回复 • 2020-07-16 17:51:39 +08:00

Mistwave

2020-07-16 12:21:18 +08:00 via iPhone

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Algorithmic%20Complexity/complexity.html

sivacohan

2020-07-16 12:22:38 +08:00 via iPhone

你这三个例子都是 O(1)
因为，输入与输出无关。

你重新看一下定义吧，你概念都理解错了。

ChanKc

2020-07-16 12:23:31 +08:00 via Android

在我看来都是 O(1)

Mutoo

2020-07-16 12:33:03 +08:00

大 O 表示法只取与当问题规模 n 趋于无穷大的时候，与 n 相关的最高次幂项。常数和低次项都可以忽略。

kilasuelika

2020-07-16 12:34:46 +08:00 via Android

考虑时间复杂度，循环范围一般是个变量。比如：
for i in range(n):
....

复杂度为 O(n)。
for i in range(n):
for j in range(i,n):
...
复杂度为 O ）

kilasuelika

2020-07-16 12:36:19 +08:00 via Android

考虑时间复杂度，循环范围一般是个变量。比如：
for i in range(n):
....

复杂度为 O(n)。
for i in range(n):
for j in range(i,n):
...
复杂度为 O(n^2)。

putaozhenhaochi

2020-07-16 12:37:25 +08:00 via Android

时间复杂度描述的是增长趋势

polaa

2020-07-16 12:37:50 +08:00

都是 O(1) ...
把 10 换为 n 的话

第一个 O(n^2)
第二个 O(n^2) ∑(i = 1~n) ∑ (j = i~n) = ∫∫ = 1/2 n^2
第三个同理

不知道算错没 QAQ

optional

2020-07-16 12:38:10 +08:00

中间的 n += 1 被执行了几次就是多少

octobered

2020-07-16 12:42:09 +08:00

都是 O1，都确定次数了
ps: 这个写成 c，放到 gcc 里开 O3 就直接 print(100)了

allenhu

2020-07-16 12:49:52 +08:00 via Android

你的运算次数没有受 n 的影响，是常量，所以是 o1

allenhu

2020-07-16 12:54:19 +08:00 via Android

举例：假设从 1 一直加到 n 求和，你需要加 n 次，此时运算次数与 n 相关了，它是 o （ n ）

necomancer

2020-07-16 13:26:38 +08:00

O(N^2), O(N^3)，上面解释很清楚了，如果你还是有困惑的话：

In [1]: s = 0

In [2]: for i in range(100):
...: for j in range(i, 100):
...: s += 1
...:

In [3]: s
Out[3]: 5050

In [4]: s = 0

In [5]: for i in range(1000):
...: for j in range(i, 1000):
...: s += 1
...:

In [6]: s
Out[6]: 500500

In [7]: s/5050
Out[7]: 99.10891089108911

In [8]: (1000/100) **2
Out[8]: 100.0

whileFalse

2020-07-16 13:46:24 +08:00

第二个是 O(n^2)，第三个是 O(\n^3)。
你先要理解一个概念：O(n/2)、O(n+100)的正确表述是 O(n)。
也就是说，以下三个算法的时间复杂度是一样的：
1. for i in range(n): dosomething(i)
2. for i in range(n/2): dosomething(i)
3. for i in range(n+100): dosomething(i)
时间复杂度取值为整个算法循环次数公式中中成长速度最快的那个部分，成长速度较低的部分被直接删除；系数全部设为 1 。
对于第二个算法，其循环次数为 n*(n+1)/2=0.5 * n^2 + 0.5 * n 。"0.5 n^2"的成长速度大于“0.5*n”，所以 0.5*n 被删除，剩下"0.5 n^2"；然后系数设置为 1，即其时间复杂度为 O(n^2)