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

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

n = 0 for i in range(10):  for j in range(i, 10):   n += 1              print(n)   // 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

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