시간 복잡도를 계산하는 방법?

Question

시간 복잡도를 계산하는 몇 가지 기본 개념을 살펴 보았습니다. 다음에 나오는 코드의 시간 복잡성을 알고 싶습니다.

시간 복잡도가 O (로그 n * n) 일 것이라고 생각합니다. 여전히 틀린 것일 수 있으며 정확한 답변과 도착 방법을 알고 싶습니다. 당신이 O (N^2)를 제공 N 반복과

function(int n){ 
    if(n == 1) return; 
    for(int i = 1; i <= n; i++) 
     for(int j = 1; j <= n; j++) 
      printf("*"); 
    function(n-3); 
    } 

Answer 1

두 중첩 루프를 :) 감사합니다. 재귀 호출은 O (n) 시간에 함수 자체를 호출합니다. 왜냐하면 상수 3에 대해 n이 감소하므로 n/3 + 1 = O (n) 번이라고합니다. 전체적으로는 O (n^3)입니다.

결과의 로그 상수는 n/3 값으로 함수가 호출되는 경우입니다.