Time Space 未排序数组中 k 最小的复杂度

Question

我解决了面试中给我的这个问题，但我不知道时间 Space 复杂度是多少。

以下解决方案的时间 Space 复杂度是多少？

// Ordered Map Method
function orderedMapFrequency(array) {
  const map = {};
  for (let i = 0; i < array.length; i++) {
    if (!map[array[i]]) {
      map[array[i]] = 1;
    } else {
      map[array[i]]++;
    }
  }
  return map;
}

function kSmallest(arr, k) {
  let map = orderedMapFrequency(arr);
  let frequencies = 0;
  for (const [key, val] of Object.entries(map)) {
    frequencies = frequencies + val;
    if (frequencies >= k) {
      return key;
    }
  }
}

// variables
let input;
let k;

input = [7, 10, 4, 3, 20, 15];
k = 3;
console.log(kSmallest(input, k)); // 7

input = [7, 10, 4, 3, 20, 15];
k = 4;
console.log(kSmallest(input, k)); // 10

input = [12, 3, 5, 7, 19];
k = 2;
console.log(kSmallest(input, k)); // 5

input = [7, 0, 25, 6, 16, 17, 0];
k = 3;
console.log(kSmallest(input, k)); // 6

我认为它可能是 O(log(n)) 还是简单的 O(n)？

Answer 1

Space 复杂度

O(N)

时间复杂度

O(NlogN)

将条目插入有序映射的时间复杂度为 O(logN)，因此从数组创建此类有序映射的时间复杂度为 O(NlogN)。因此，您的 orderedMapFrequency 是 O(NlogN)。通过遍历有序映射找到第 k 个最小元素的时间复杂度为 O(k)，这主要取决于有序映射的创建。因此整体时间复杂度为 O(NlogN).

附录

您可以检查 here 以找到时间复杂度更好的解决方案。
有趣的是 Javascript 中的对象 {} 充当整数键的有序映射，参见 :

Integer indices (if applicable), in ascending order.

Answer 2

您的解决方案使用了 JavaScript objects 的特征：indexes 的十进制表示的键将在调用函数时按排序顺序迭代，例如Object.entries.

从规范中我们只能了解到设置和获取object属性必须具有sub-linear时间复杂度（参见Javascript ES6 computational/time complexity of collections），因此，这些操作运行在常数时间内并不是语言的绝对要求。

如果这些在时间上是恒定的，并且对这些属性的迭代将花费线性时间，那么我们会找到一种在线性时间内对数字进行排序的方法，这是不可能的除非有一些限制允许 non-comparative 排序算法，例如 radix sorting algorithms.

这里有限制：object 键仅在这些数字是 0 到 2 范围内的整数时按其数字顺序迭代³¹-1。所以这不适用于：

负值
小数
大于 2 的数字³¹-1（另请参阅 Object.keys order for large numerical indexes?）

这样的键将在其他数字之后迭代，按照它们被插入的顺序（对于根本不是数字表示的键也会发生这种情况）。所以当这种情况发生时，你的解决方案可能会产生错误的结果。

这里是您的代码运行，对违反上述条件之一的稍作调整的输入：

let input, k;

input = [7, 10, 4, -3, 20, 15]; // Notice -3
console.log(kSmallest(input, 3)); // 10 (should be 7)

input = [7, 10, 4, 3.1, 20, 15]; // Notice 3.1
console.log(kSmallest(input, 4)); // 15 (should be 10)

input = [12000000000, 3000000000, 5000000000, 7000000000, 19000000000]; // Big numbers
console.log(kSmallest(input, 2)); // 12000000000 (should be 5000000000)

// Your functions (unchanged)
function orderedMapFrequency(array) {
  const map = {};
  for (let i = 0; i < array.length; i++) {
    if (!map[array[i]]) {
      map[array[i]] = 1;
    } else {
      map[array[i]]++;
    }
  }
  return map;
}

function kSmallest(arr, k) {
  let map = orderedMapFrequency(arr);
  let frequencies = 0;
  for (const [key, val] of Object.entries(map)) {
    frequencies = frequencies + val;
    if (frequencies >= k) {
      return key;
    }
  }
}

如您所见，输出并不是您预期的 k 最小值。

如果目标是让算法在这些情况下也能正常工作，那么您不能再依赖 JavaScript objects 的这种特定行为和属性迭代顺序像 Object.entries 这样的函数，你必须想出一个明确编写的算法（例如使用堆数据结构），如果做得好，它的时间复杂度将是 O(nlogk)。

至于算法的时间复杂度：它取决于 JavaScript 引擎，但似乎许多引擎在为 get/set 操作提供接近恒定的时间复杂度方面做得很好83=] 键 collections。因此，这意味着您的解决方案在实践中提供了 O(n) 时间复杂度。但是：

允许 JavaScript 实现为 get/set 键 collections 上的 get/set 操作提供 O(logn) 时间复杂度，因此您的解决方案具有 O( nlogn) 时间复杂度。
above-mentioned 限制使得任何关于时间复杂度的陈述都变得没有意义。

space 复杂度微不足道：O(n)。

Time Space 未排序数组中 k 最小的复杂度

Time Space Complexity of k smallest of unsorted array

javascript

sorting

algorithm

time

space