算法分析：大O /最壞情況

Question

一門功課的問題問我來分析下面的代碼fragement：

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

我認爲內循環運行以下次數：

N + (N-1) + (N-2) + ... + (N - N + 1) 

然而，我無法將其轉換爲O（）表示法。

難道有人指着我正確的方向嗎？

Answer 1

通過觀察，內循環運行1 + 2 + ... + N次。這正是N（N + 1）/ 2（這是三角形數字的公式）。首先，記住big-O的定義：如果| f/g |，f就是O（g）是足夠大的N.因此，例如，這是O（exp（n）），它也是O（n^3）。它也是O（N（N + 1）/ 2），但是你的老師可能期望答案O（N^2）。如何證明這是O（N^2）？ Well（N（N + 1）/ 2）/ N^2是1/2 + 1/2N。對於N> 0，這以1爲界。