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

[smallyu]

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

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

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

[Mistwave]

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

[sivacohan]

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

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

[ChanKc]

在我看来都是 O(1)

[Mutoo]

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

[kilasuelika]

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

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

[kilasuelika]

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

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

[putaozhenhaochi]

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

[polaa]

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

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

不知道算错没 QAQ

[optional]

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

[octobered]

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

[allenhu]

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

[allenhu]

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

[necomancer]

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]

第二个是 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)

[raysonx]

反对 13 楼和 14 楼都答案。题主的代码复杂度均为 O （ 1 ）。

按照循环层数猜测复杂度是典型的民科。楼主可以看一下堆排序算法中建堆的复杂度为什么是 O （ n ）。

[w99w]

O(n)

[w99w]

另外，楼主你的写法就不太对。
一般不是 n+=1,而是 n+=i
1~n 相加整个运算过程需要计算 n 次加法。
所以是 O(n)

[wellsc]

常量 1

[iseki]

我记得他们讲大 O 符号的时候讲了下θ渐进符号 emmm，取最高次项幂？

[newtype0092]

如果你是想求等差数列的复杂度，
(1+n)*n/2 = n^2/2 + n/2
复杂度只看 n^2

[newtype0092]

我也被自己绕昏了，看起来确实是 O(1)啊

[SiliusMo]

从 1 加到 10 这个代码里都没有 n. 哪里来的 O(n)?
无论你套几层循环，需要的步骤都是常量, 所以结果是 O(A). A 代表一个常数. 其实也就是 O(1).

[ourFEer]

O(1)

[wnpllrzodiac]

复杂度和 指令优化是两个概念。虽然现在编译器智能了，而且机器性能高了，很多东西都不需要人考虑了