時間這個特定的算法

的複雜性原諒我，如果有什麼我要問的是顯而易見的，但我一直在考慮這個問題2小時！我只是無法弄清楚....時間這個特定的算法

嗯，我有類似這樣：

for(int i=0;i<N;i++) 
    for(int j=0;j<i;j++)

我可以肯定的說，複雜度爲O（N +（N-1）+（ N-2）...），但有這種類型的一個簡單的符號？

由於

檢查[這個答案]（http://stackoverflow.com/questions/13621550/a-puzzle-related-to-nested-loops/13622284#13622284）它涵蓋你的答案。它是從N N^2 –

總和爲1爲n *（N + 1）/ 2，其爲O（N * N），因爲O（1/2）僅僅是恆定 –

@huseyintugrulbuyukisik添加一個答案。 –

注意的是：

首先相互作用：1個執行命令行

第二交互：2個執行命令行的

...

第N相互作用：在命令行

=總和1 + ... N個執行N =算術級數=總和（N/2）（1 + N）

因此，O（N^2）。

2014-02-15 10:20:28 DanielTheRocketMan

從1到n

和等於N（N + 1）/ 2 = N * N/2 + 1/2的漸近符號的千卡它是O（n^2）其餘應該清楚我想

2014-02-15 10:20:04 Vilen

回答