이 알고리즘의 시간 복잡도는 얼마입니까?

Question

다음 코드는 복잡성 O (n^3)가 있다고 생각하지만 시간 복잡성은 O (n)이라고 생각합니다.

편집 : 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) 때문에 트리플 루프이다. 내 논리는 3 중 루프를 사용하더라도 해시를 넘어 철저한 것입니다. 해시의 각 요소는 기본적으로 3- 튜플 (k1, k2, k3)에 의해 인덱싱됩니다. 일반적으로 3 개의 깊은 루프를 통과하는 것은 O (n^3)가 될 것이지만, 해시의 각 레벨은 희소 배열로 작용하므로 해시에 추가하면 같은 레벨의 다른 해시에는 영향을 미치지 않습니다. , 또는 다른 레벨의 다른 해시까지도 포함 할 수 있습니다.

Answer 1

가 나는 트리 구조 방법에 대한 증거를 사용하고는 O (n은)