다음과 같은 시간 복잡성은 무엇입니까?

Question

이 유형의 많은 질문을 보았습니다. 그러나 반복을 분명히 할 수는 없습니다.

for i=1...n 
for j=1..i 
    k=n 
    while (k>2) 
    k=k^(1/3) 

Answer 1

두 for 루프 O(n^2) 결합하고, 내부 루프는 O(log2(log2(n))이다 [*]. 따라서 전체적인 복잡도는 O(n^2*log2(log2(n)))입니다.

이

n = 2^(3^m) 

이 일관성을 위해 동일한 로그 기반을 사용하여 (O(log2(log2(n))과 동일 log3(log2(n))를 제공합니다

은 내부 루프의 반복 m의 번호를 찾으려면 우리는 m에 대해 다음을 해결하기 위해 필요).

[*] 사용자의 표기로 k^(1/3)이 k의 큐브 루트라고 가정합니다.