這個算法的時間複雜度是多少？

我相信下面的代碼具有時間複雜度O（n），而我的朋友認爲它具有複雜度O（n^3）。這個算法的時間複雜度是多少？

編輯：n爲元素的數據

var hash = {} 
for (var element in data) { 
    var k1 
    var k2 
    var k3 
    // ... stuff 
    if (!hash[k1]) { 
    hash[k1] = {} 
    } 
    if (!hash[k1][k2]) { 
    hash[k1][k2] = {} 
    } 
    if (!hash[k1][k2][k3]) { 
    hash[k1][k2][k3] = 0 
    } 
    hash[k1][k2][k3] = hash[k1][k2][k3] + 1 
} 

for (var k1 in hash) { 
    for (var k2 in hash[k1]) { 
    for (var k3 in hash[k1][k2]) { 
     // really do stuff 
    } 
    } 
}

什麼是該算法的時間複雜度是多少？

編輯：n爲元素的數據

數量

編輯：所以，我的朋友的推理，這是O（n^3）是因爲三環路。我的推理是，即使對於三重循環，它也是散列在哈希上，沒有更多。散列中的每個元素基本上由三元組（k1，k2，k3）索引。雖然正常遍歷一個3深的循環將是O（n^3），我相信散列的每一級功能都是一個稀疏數組，我的意思是，添加到散列不會影響同一級別的其他散列，甚至其他級別的其他哈希。

來源

2014-10-01 user3288049

這可能屬於代碼審查 – juvian 2014-10-01 17:21:05

什麼'N'？另外，爲什麼你不包括你的分析顯示代碼是'O（n）'（也可能是你的朋友的）？ – NPE 2014-10-01 17:21:07

我認爲你忽略的「東西」是理解這一點的關鍵。在這裏你可以免費使用這些，因爲我有很多額外的東西：'; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;' – Pointy 2014-10-01 17:22:23

我用它是如何樹形結構的證明和用於樹木一般歸納證明，以表明它是O（n）的

來源

2014-10-03 13:58:46 user3288049

這個算法的時間複雜度是多少？

回答

相關問題