給定一個數組嵌套算法

Question

的計算複雜度[1,2,3,4,5,6,7,8,9,10]假設我們有一個算法，執行以下操作：

for i in 0..a.length 
    for j in 0..a.length 
    ... 

這將具有O（n^2）的大O運行時間，因爲對於每個元素它將遍歷整個數組。

但是如果內循環只從外部索引向前運行會怎樣？

for i in 0..a.length 
    for j in i..a.length 
    ... 

也就是說，比較起來，第一個算法每次迭代都會看n個元素（外部循環）。第二ALGO着眼於：在第二次迭代上的第一迭代

• n個元素
• n-1個元素
• 在第三次迭代
• n-2個元素...
• 1元素在最後一次迭代

在計算這種算法的Big O運行時，它仍然是O（n^2）嗎？

Answer 1

這仍然是O（n^2）。總和1 + 2 + ... + n是n（n + 1）/ 2，它是O（n^2）。更一般地，對於任何多項式函數p（n），p（1）+ p（2）+ ... + p（n）的和爲O（n p（n））。這個證明要困難得多，因爲你必須推理n的任意冪的和，但它的確如此。這意味着，例如，如果將內部循環的第三個循環嵌套到範圍從j到n的內部循環中，則運行時將爲O（n^3）。

Answer 2

如果給出a是特定數組，那麼該算法的時間複雜度是恆定的（或O（1））。也許我從字面上理解了你所要求的內容，但是對於最緊密的界限是O（n^2），a必須是一個像[1,2，...，n]這樣的數組。如果a明確規模爲10，那麼算法總是以相同的步數運行。

希望這個答案是不必要的，但我是一個離散數學課堂的助教，我們給出了非常類似於這個問題的技巧問題。如果我誤解了這個問題，那麼我很抱歉浪費你的時間！此外，已發佈的答案非常好！