我在面試中解決了這個問題，但我不知道時空復雜度是什么。
以下解決方案的時空復雜度是多少？
// 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)？
uj5u.com熱心網友回復：
空間復雜度
在）
時間復雜度
O(NlogN)
將條目插入有序映射是 O(logN)，因此從陣列創建這樣的有序映射是 O(NlogN)。orderedMapFrequency因此你是 O(NlogN)。通過遍歷有序映射找到第 k 個最小元素是 O(k)，這取決于有序映射的創建。因此總的時間復雜度是 O(NlogN)。
附錄
您可以在此處查看以找到具有更好時間復雜度的解決方案。
有趣的是
{}，Javascript中的 Object充當整數鍵的有序映射，請參閱ES6 是否為物件屬性引入了定義良好的列舉順序？：
整數索引（如果適用），按升序排列。
uj5u.com熱心網友回復：
您的解決方案使用JavaScript的特性物件：是的十進制表示關鍵指標將在有序呼叫類的函式時迭代Object.entries。
從規范中我們只能了解到設定和獲取物件屬性必須具有亞線性時間復雜度（參見Javascript ES6 計算/集合時間復雜度），因此這些操作在恒定時間內運行并不是語言的絕對要求。
如果這些在時間上是恒定的，并且對這些屬性的迭代將花費線性時間，那么我們將找到一種在線性時間內對數字進行排序的方法，這是不可能的，除非應用一些限制，這將允許非比較排序演算法，例如作為基數排序演算法。
并且這里有一些限制：物件鍵僅在這些數字是 0 到 2 31 -1范圍內的整數時才按其數字順序迭代。所以這不適用于：
- 負值
- 小數
- 大于 2 31 -1 的數字（另請參閱Object.keys 的大數字索引順序？）
這些鍵將按照插入的順序在其他數字之后迭代（對于根本不是數字表示的鍵也會發生這種情況）。因此，當發生此類情況時，您的解決方案可能會產生錯誤的結果。
這是在稍微修改的輸入上運行的代碼，這些輸入違反了上述條件之一：
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 -smallest。
If the aim is for the algorithm to work also in those cases, then you can no longer rely on this specific behaviour of JavaScript objects and the property iteration order of functions like Object.entries, and you'll have to come up with an explicitly written algorithm (like for example using a heap data structure), which will have O(nlogk) time complexity if well done.
As to the time complexity of your algorithm: it depends on the JavaScript engine, but it seems many do a good job in providing near constant time complexity for the get/set operations on object key collections. So that would mean your solution provides a O(n) time complexity in practice. But:
- A JavaScript implementation is allowed to provide O(logn) time complexity for get/set operations on object key collections, so then your solution has a O(nlogn) time complexity.
- The above-mentioned restrictions make any statement about time complexity less meaningful.
The space complexity is trivial: O(n).
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/339870.html
標籤：javascript 算法 排序 时间 空间