-3

这是我用于简单选择排序的代码。通常，排序的复杂性（时间）是在选择排序的情况下排序 O(n^2) 所花费的迭代次数当我针对 98765 的示例字符串干运行此代码时，它给了我 25 次迭代。只是为了交叉检查我的空运行输出，我在我的代码中放了 2 个 vbl-noi 和 noj。

Q：总迭代次数是=noi*noj还是noi+noj；

int index = 0; int noi = 0, noj = 0;

for (j = 0; j < 5; j++)
{
    noj++;
    index = j;
    for (i = j; i < 5; i++)
    {
        if (a[index] > a[i])
        {
            a[index] = a[index] + a[i];
            a[i] = a[index] - a[i];
            a[index] = a[index] - a[i];
            noi++;
        }

    }

}
4

3 回答 3

2

迭代次数始终为 15 (5+4+3+2+1)，因为在您的循环中有j<5and i<5。所以你的代码复杂度是 O(n^0) 因为在你的情况下 n 是 5

于 2012-12-10T11:50:00.420 回答
2

复杂性不依赖于，n因为没有n. 复杂度总是正好是 15（1+2+3+4+5 表示 shift66）

于 2012-12-10T12:03:29.463 回答
0

它是： noj [对于第一个循环] + (( noj * (noj + 1) ) / 2) [对于内部循环]

因为第一个循环来自 1-noj，第二个是 j-noj（其中 j 取决于第一个循环）

于 2012-12-10T12:01:49.947 回答