해시 테이블 조회로 쿼드 중첩 루프에 대한 큰 세타

Question

for (int i = 0; i < 5; i++) { 
    for (int j = 0; j < 5; j++) { 
     for (int k = 0; k < 5; k++) { 
      for (int l = 0; l < 5; l++) { 
       look up in a perfect constant time hash table 
      } 
     } 
    } 
} 

큰 실행 시간은 무엇입니까?

어둠 속의 가장 좋은 추측 : 나는 항상 중첩 된 for 루프가 O (n^k) 인 것을 봅니다. 여기서 k는 루프의 수이므로, 루프는 O (n^4)가 될 것입니다. 나는 일정 시간 동안 O (1)을 곱한다? 이 모든 것이 큰 세타가 될 것입니까?

Answer 1

큰 세타 실행 시간은 Θ(n^4)입니다.

Big-O는 위쪽 경계이며 big-theta는 긴 경계입니다. 이것이 의미하는 바는 코드가 O(n^5)이라면 정확하지만 (Θ(n^5)은 아님) 큰 -O 내부의 내용은 점근 적으로 n^4 이상이어야합니다. I는 5 가정있어

가없는 경우 5^4가 일정하기 때문에, 루프는, 일정 시간 (O(1) 및 Θ(1))에서 실행되는 것 (즉 n이다) 다른 값으로 대체 될 수있다.

Answer 2

해시 테이블에 액세스하는 것이 실제로 theta (1)라고 생각하면 해시 테이블에서 상수 (5^4) 조회 만하기 때문에이 알고리즘은 theta (1)에서도 실행됩니다.

그러나 5를 n으로 변경하면 정확히 n^4의 상수 시간 연산을 수행하기 때문에 theta (n^4)가됩니다.

Answer 3

사용 시그마 표기 :

실제로

가장 안쪽 루프 내부 설명은 625 번 실행된다.