我试图分析下面的代码。我希望计算复杂性和操作/迭代次数（这会导致复杂性）。我猜复杂性是o（n^2），因为我已经嵌套了for循环。但是，在内部循环中，值正在切换，替换位置。这个操作是不是会使算法重复多次，因此它不止是o（n^2），或者只可能有while循环？如何找到所完成的迭代/操作的确切数目？
for (int i = 0; i < b.Length; i++)
{
for (int j = i + 1; j < b.Length; j++)
{
if (b[i] > b[j])
{
t = b[i];
b[i] = b[j];
b[j] = t;
}
}
}
2条答案
按热度按时间j0pj023g1#
循环的数量由
b.length它是一个常数，索引变量i和j。只要你不在循环中干涉i和j，复杂性就保持不变。zi8p0yeb2#
外环有
b.length迭代。我们称之为n.内环有
n - i - 1迭代。内部循环的总迭代次数为
内部循环的每次迭代都会执行常量工作（最多1个条件+3个赋值），因此总运行时间为
O(n^2).操作的确切次数取决于输入，因为输入决定条件为真的次数。