9번 모두의 약수 코드와 처음에 알려주신 반복문 코드 차이가 무엇인가요?

시간복잡도라 하면 연산의 횟수를 구하는 거라 생각하면 되겠습니다.

처리할 데이터의 크기가 n이고, 연산의 횟수를 구해주는 함수를 T(n)이라고 하겠습니다.

▣ 첫 번째 경우:

for(i=1; i<=n; i++){  //n회 반복

    for(j=1; j<=i; j++){  //평균 (n+1)/2 회 반복

           연산;

    }

}

위 코드의 T(n)=n*(n+1)/2 이고 Big-O 표기법은 차수가 낮은 항들과 계수를 무시하고 표현하므로 O(n^2)이라 합니다.

▣ 두번째 경우 : 

for(i=1; i<=n; i++){   //n회 반복

    for(j=1; j<=n; j=j*2){   //log n(밑은 2) 반복

            연산;

    }

}

위 코드의 경우 T(n)=n*logn 이고 Big-O 표기법으로는 O(nlogn)입니다.

for(i=1; i<=n; i++){  //n회 반복

    for(j=1; j<=n; j=j+i){ // n/i 회 반복 

           연산;

    }

}

코드의 경우 T(n)의 식을 n에 관한 다항식으로 표현하기 힘듭니다만 j 가 i의 증가율로 증가하므로 

위 코드가 "▣첫 번째 경우"의 코드 보다는 성능이 좋고 "▣두번째 경우"의 코드 보다는 성능이 떨어집니다.

즉 위코드의 성능이 O(n^2)과 O(nlogn)사이에 있으며 제가 봤을 때는 위 코드의 성능이 O(nlogn)에

가깝다고 생각합니다. 영상에서는 이정도의 근거로 제 느낌을 얘기한 것입니다.

감사합니다. 도움이 되도록 노력하겠습니다.

항상 친절한 답변 정말 감사합니다. 포기하지않고 알고리즘 공부 열심히 할 수 있을것 같습니다 !