javascript - 为什么基数排序的大 O 不是二次的？

Question

function getDigit(num, i) {
  return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

function digitCount(num) {
  if (num === 0) return 1;
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

function mostDigits(nums) {
  let maxDigits = 0;
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(nums[i]));
  }
  return maxDigits;
}

function radixSort(nums){
    let maxDigitCount = mostDigits(nums);
    for(let k = 0; k < maxDigitCount; k++){
        let digitBuckets = Array.from({length: 10}, () => []);
        for(let i = 0; i < nums.length; i++){
            let digit = getDigit(nums[i],k);
            digitBuckets[digit].push(nums[i]);
        }
        nums = [].concat(...digitBuckets);
    }
    return nums;
}

这就是我学到的基数排序代码。但是如果你看 radixSort 函数，里面的 for 循环是嵌套的，据我所知，这意味着基数排序的大 O 是 O(n 2)。但是根据我学到的材料，它说基数排序的时间复杂度是O(nk)。n 是数组的长度，k 是位数（平均）。我不知道为什么它不是 O(n 2)。

标签： javascriptalgorithm

Answer 1

在计算机科学中，大 O 表示法用于根据算法的运行时间或空间需求随着输入大小的增长而增长来对算法进行分类。

基数排序具有线性复杂度O(nk)。这是因为k是常数（位数），并且n可以增长（数组的长度）。

k影响函数的斜率，但它远不是 O(n ² ) 复杂度（图 n=1 到 30）：