这个算法的时间复杂度是多少？

我相信下面的代码具有时间复杂度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

这个算法的时间复杂度是多少？

回答

相关问题