如何判斷這些嵌套語句執行多少次？

我有以下僞代碼：如何判斷這些嵌套語句執行多少次？

SelectionSort(A) 
    n = A.length 
    for j=1 to n-1 
     smallest = j 
     for i=(j+1) to n 
      if A[i] < A[smallest] 
       smallest = i 
     exchange A[j] with A[smallest]

我認爲第一for循環測試將執行n次，並且嵌套for循環將執行1 + 2 + ... + N = N（N +1）/ 2次（如果我錯了，請糾正我）。但我不明白我怎麼知道嵌套的if語句會執行多少次？是1/2 * n（n + 1）/ 2嗎？

來源

2015-06-12 Ali Mustafa

外部for-loop將運行n次。但是，它也包含一個依賴於j的值的內部for循環。

我認爲第一for循環測試將執行n次，並嵌套在 for循環將執行1 + 2 + ... + N = N（N + 1）/ 2次。基於外for循環的所有迭代

內部的for循環將運行第（n-1）+（N-2）+ ... + 1次。因此，循環語句的網絡迭代將是（n-1）+（n-2）+（n-3）+ ... + 1 =（n-1）* n/2 =（n -n）/ 2次。

但我不明白我怎麼能告訴嵌套的 if語句將執行多少次？是1/2 * n（n + 1）/ 2嗎？

由於inner-if語句依賴於數組元素，所以不可能直接確定它將運行多少次。

但是，這是肯定的，在最壞情況，因爲它是位於內for循環的if語句，可能執行的最大數量（在最壞的情況下），將（N -n）/ 2次。

所以，如果語句的執行最壞情況下的複雜度是 爲O（n ）

來源

2015-06-12 06:18:28

但不會內循環運行N次第一迭代外環，當j = 1時？ –

@ AliMustafa-No，因爲我的值將被設置爲2（因爲i = j + 1），這意味着它將迭代從i = 2到i = n的循環，意味着共有n-1次迭代。 –

好的，你能否看到我是否正確：外部for-loop頭執行n次，外部for循環體執行n-1次？內部for-loop頭執行n次，內部for循環體執行n-1次？當j = 1時 –

外環將從1運行到n-1，因此n-1次。
內循環應從j + 1到n次運行。這意味着當j是1時，它將運行2到n次（n-1次），當j是n-1時，它將運行n到n次（1次）。因此，內循環應運行（n-1 + n-2 + ... + 1）次= n（n-1）/ 2次。

if語句的執行次數與內循環的次數相同。當然條件陳述應取決於有條件的結果。

來源

2015-06-12 06:17:25

如何判斷這些嵌套語句執行多少次？

回答

相關問題