다음 코드 단편의 시간 복잡도를 찾는 방법

Question

다음 코드 단편의 시간 복잡도와이를 계산하는 방법은 무엇입니까?

function(int n){ 
     for(int i = 1 ; i<=n ; i++){ 
      for(int j=1 ; j<=n; j+=i){ 
       System.out.println("*"); 
     } 
    } 

Answer 1

전체 작업을 생각해 봅시다. 주석에서 언급했듯이 내부 루프는 i = 1이면 n 번, i = 2 일 때는 n/2 번, i = 3 일 때는 n/3 번 (반올림 오류 무시)으로 실행됩니다. 이 수행 전체 작업을 의미

N + N/2 + N/3 + N/4 + ... + N/N

N = (1 + 2 + 1/3 + 1/4 + ... + 1/N)

괄호 안의 항은 nth harmonic number이고, n H _{표시하므로 전체적인 일된 대략 N} nH의 _{이다. H n = Θ (log n)이므로 총 작업 시간은 Θ (n log n)입니다.}