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

Question

9번 #include using namespace std; int main(void) { int num,i,j=1; int sum; scanf("%d",&num); if(num>=5 && num <=50000) for(i=1;i<=num;++i) { sum=0; for(j=1;j<=i;++j) { if(i%j==0) sum++; } printf("%d ",sum); } } }이런식으로 코딩하면 n제곱이라고 알려주셨는데 반복문이 2개써서 n의 제곱인가요?? 선생님이 알려주신 시간이 더 적게 드는 방법도 반복문이 2개인데 이것의 시간복잡도를 구하는 방법은 없는건가요? 어떻게해서 nlog n보다는 덜 하다는 걸 구하셧는지 소스를 보고 시간복잡도를 대략적으로 구하는 방법이 궁금합니다!

김태원 · Answer

시간복잡도라 하면 연산의 횟수를 구하는 거라 생각하면 되겠습니다. 처리할 데이터의 크기가 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)에 가깝다고 생각합니다. 영상에서는 이정도의 근거로 제 느낌을 얘기한 것입니다.

김태원 · Answer

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

blizzarduser · Answer

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