如何计算数组原地频率统计代码的时间复杂度？

先贴出原代码：

int arr[] = {4, 5, 6, 8, 1, 2, 3 , 4, 1, 2, 5};
int size = sizeof(arr) / sizeof(arr[0]);

cout << "size: " << size << "\n";

for(int i = 0; i < size;) {
    if(arr[i] > size) {
        arr[i] = 0;
        i++;
    }
    if(arr[i] <= 0) {
        i++;
        continue;
    }
    int indexToUpdate = arr[i] - 1;
    if(arr[indexToUpdate] < 0) {
        arr[i] = 0;
        arr[indexToUpdate]--;
        i++;
    } else {
        arr[i] = arr[indexToUpdate];
        arr[indexToUpdate] = -1;
    }
}
for(int i = 0; i < size; i++) {
    cout << i << " : " << arr[i] << "\n";
}

时间复杂度计算过程 #

我们把代码拆成两个核心部分分析：

1. 数组处理循环 #

这个循环的i并非每次迭代都递增，但关键是每个数组元素最多被常数次操作处理完毕：

• 若元素大于数组长度size，直接置0后i递增，属于O(1)操作；
• 若元素是负数或0，直接跳过、i递增，也是O(1)；
• 若元素是有效正数：
  • 若目标索引（arr[i]-1）的元素已为负数（代表已统计过频率），则把当前元素置0、目标元素减1（频率+1）后i递增，O(1)；
  • 若目标索引元素是正数，则把当前元素替换为目标元素的值，同时把目标元素设为-1（标记已统计一次）——此时i不递增，但这只是把目标元素的值“转移”到当前位置，后续会继续处理这个值，但每个元素只会被这样转移一次，因为一旦目标元素被设为负数，就不会再被转移了。

整个数组的每个元素只会被处理有限次（最多2-3次），因此这个循环的时间复杂度是O(n)（n为数组长度）。

2. 结果输出循环 #

这个循环就是单纯遍历整个数组一次，每个元素做一次输出操作，时间复杂度显然是O(n)。

总时间复杂度 #

将两个部分的时间复杂度相加，O(n) + O(n) = O(n)，属于线性时间复杂度。

内容的提问来源于stack exchange，提问作者princegoyal-dev