这里的复杂度分析是否正确呢？时间复杂度是 O(n) 还是 O(n^2)?
来源：2-6 均摊时间复杂度分析（Amortized Time Analysis）
小奇mack
2018-12-03
输入正文
有一个整形数组，包含正数和负数，然后要求把数组内的所有负数移至正数的左边，且保证相对位置不变，要求时间复杂度为O(n), 空间复杂度为O(1)。
```
package com.avl.arithmetic.Other;
public class Problem01
{
private static int[] datas = {10, -2, 5, 8, -4, 2, -3, 7, 12, -88, -23, 35};
/**
* 时间复杂度： n + 负数个数m*每个移动的步数k = O(n+m*k)
*由于m和k是变化的，按照平均复杂度计算 依然是O(n)
* 空间复杂度： O(1) 只用到了一个负数的计数器count；
* @param args
*/
public static void main(String[] args) {
int count = 0;
for (int i = 0; i < datas.length; i++) {
if (datas[i] < 0)
{
int step = i - count;
for (int j = i; j > i - step; j--)
{
int temp = datas[j];
datas[j] = datas[j - 1];
datas[j - 1] = temp;
}
count++;
}
}
for (int i = 0; i < datas.length; i++)
{
System.out.print(datas[i] + " ");
}
}
}
//输出结果：
-2 -4 -3 -88 -23 10 5 8 2 7 12 35
```
1回答
-
这段代码时间复杂度是O(n^2)的：）
“按照平均复杂度计算，依然是O(n)”，这句话一带而过，但怎么平均的，完全没有说，实际上这个叙述是错误的。这段代码的本质是冒泡。如果这段代码是O(n)的，冒泡就不是O(n^2)的算法了：）
在最坏情况下，正负数交替存在，比如[-1, 2, -3, 4, -5, 6, ... ]
按照这个算法，第一个负数移动0步，第二个负数移动1步，第三个负数移动2步...
n/2个负数移动 0 + 1 + 2 + .. + n/2步，是O(n^2)的。
012018-12-13
相似问题