我怎么知道这些嵌套语句将执行多少次？

Question

我有以下伪代码：

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 吗？

Answer 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 语句的执行次数应与内循环相同。当然条件语句应该取决于if条件的结果。

Answer 2

外部 for 循环将运行进行 n 次。但是，它还包含一个内部 for 循环，该循环取决于 j 的值。

I think that the first for-loop test will execute n times, and the nested for-loop will execute 1 + 2 + ... + n = n(n+1)/2 times.

内部for循环将运行 (n-1)+(n-2)+...+1次基于外部for循环的所有迭代。因此，循环语句的净迭代组合为 (n-1) + (n-2) + (n-3) + ... + 1 = (n-1)*n/2 = ( n²-n)/2次.

But I don't understand how I can tell how many times the nested if-statement will execute? Is it 1/2 * n(n+1)/2 ?

由于inner-if 语句依赖于数组元素，因此无法直接确定它究竟会执行多少次运行。

但是，可以肯定的是，在最坏的情况下，由于它位于内部for循环中，if语句的最大可能执行次数（在最坏情况下）将是（ n²-n)/2 次。

So, the worst-case complexity of execution of if-statement is O(n²)

我怎么知道这些嵌套语句将执行多少次？

How can I tell how many times these nested statements will execute?

algorithm

sorting

big-o

time-complexity

complexity-theory