void func(int n)
for (inti=0;i<10000;i++)
for (int j =0;j<n;j++)
for (intk=0;k<i;k++) printf("%d",k);
for(int k=0;k<j;k++) printf("%d".k);
여기서 n에대한 시간복잡도를 구하려면
1번째포문= 상수니까 o(1)
2번째 포문= n이니까 o(n)
3번째 포문= 1부터 10000까지 더한항 즉 o(1)
4번째 포문= j값에따라달라짐 근데 j값이 0부터 n-1까지 점점 증가하면서 k에 대한 포문을 계속 돌리기때문에 n(n-1)/2=o(n^2)
결국 젤 안쪽에위치한 포문의 변수가 시간복잡도를 결정하기때문에 o(n^2) 라고 생각하면 괜찮을까요..? 아니면 혹시 더쉬운방법으로도 풀수있는지 제생각이 틀렸는지 궁금합니다 감사합니다!
- dc official App
제일 영향을 많이 주는 부분을 생각해보셈 안쪽 포문이 O(N^2) 라서 O(N^2) 라 생각하면 ㅈㄴ 쉬움
아무래도 저런걸 구할때는 안쪽포문이 제일 중첩된거니 물론 바깥포문에 의해 안쪽 k변수가 1부터 n까지 더해져서 n제곱이지만 저런경우는 그냥 이중포문이고 안쪽 변수 또한 나눠지고 그런게 없으니 n^2이라고 외워두면 편할까요?!?! 답변 감사합니다! - dc App
시간 복잡도 자체가 실행 시간에 영향을 제일 많이 부분을 대변하는거라 본문처럼 for문 하나하나 생각하면서 복잡도 계산하는거보다 저렇게 생각하는게 더 쉬움
아 그런거군요! 감사합니다!!!! - dc App
1 *n ㄴ1* n n^2 잘 계산 했구만
뭔가좀 복잡하게 푸는 경향이 있어서요 ㅠㅠㅠ 좀빠르게 풀고싶은데 그냥 젤 안쪽포문 변수에의해 시행횟수가 변하는 for문만 계산하는게 최선일지 궁금해서..ㅠㅠ - dc App