인프런 커뮤니티 질문&답변
작성자 없음
작성자 정보가 삭제된 글입니다.
9번 모두의 약수 코드와 처음에 알려주신 반복문 코드 차이가 무엇인가요?
작성
·
245
0
9번
#include <iostream>
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보다는 덜 하다는 걸 구하셧는지 소스를 보고 시간복잡도를 대략적으로 구하는 방법이 궁금합니다!
답변 3
3
시간복잡도라 하면 연산의 횟수를 구하는 거라 생각하면 되겠습니다.
처리할 데이터의 크기가 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)에
가깝다고 생각합니다. 영상에서는 이정도의 근거로 제 느낌을 얘기한 것입니다.
0
0
