运行迭代排序算法的时间分析

Question

我正在学习如何为算法的运行宁时间编写理论分析，我想知道对于以下代码这样说是否正确：

while(high >= low) {
     loop body here....
     high--;
     low++;
}

对于 N 个整数的数组，低从索引 0 开始，高从索引 N - 1 开始。循环体将进行运行 (n / 2) times 或 (n / 2) + 1 比较。这样说对吗？如果是这样，为了获得整个函数的完整运行时间分析，您是否会评估任何内部循环以创建运行时间的完整函数？

Answer 1

在您代码的 loop body here..... 代码部分，您可能有一些其他循环运行一些 f(n) 的复杂性。如果 n 是偶数，给定的 while 循环将执行运行 n / 2 次，如果 n 是偶数，则执行 (n / 2) + 1 次n 是奇数。

所以，外层循环的运行ning 时间复杂度就是 O(n / 2) = O(n).

现在，

如果 loop body here..... 代码段在摆弄 high and/or low，那么这个 while 循环的复杂度会有所不同。
如果 loop body here..... 代码部分是 O(1) 并且它不修改 high and/or low，那么整体运行-时间是 O(n).
如果 loop body here..... 代码部分是 O(n) 并且它不修改 high and/or low，那么整体运行-时间是 O(n²).
一般来说，如果loop body here.....代码段是O(f(n))并且不修改highand/orlow，那么整体运行-时间是O(n * f(n)).

Running Time Analysis for Iterative sorting algorithm