[일반] 시간복잡도 계산법 이거 맞을까요?

[익명(14.39)]

시간복잡도 계산 공부좀 해보려는데 이게 맞는가 싶어서요

for(int i=0; i<n; i++) {    // O(N)

   for(int j=0; j<i*i; j++) {   // O(N^2)

     for(int k=i; k>0; k-=1) {  // O(N)

      }

   }

}

총 O(N^4)이 맞을까요..?

[익명(223.62)]

가장 안쪽 포문에서 k값이 최대 i*i 부근이니까 제일 안쪽도 O(n^2) 가 되서 총 O(n^5) 아니려나요? 초보여서 확실하지는 않음

[익명(223.62)]

아잘못봤네 님이 말한게 맞는듯

[익명(14.39)]

아!? 공부중이시군요.. 다른분들 의견도 좀 더 들어봐야겠네요.. 맞는거같기도하고 어떤분은 O(n^3)이라고 얘기하셔서...

[익명(223.62)]

i가 N에 가까워졌을때 두번째 포문은 사실상 j가 N^2에 가까워지니 두번째 포문은 확실히 O(N^2)가 맞는것 같아요 연산량이 제곱만큼임

[익명(14.39)]

의견 감사요!

[익명(183.100)]

저런거는 제일 안쪽에 변수++시키고 나중에 변수값보면 됨

[익명(183.100)]

보니까 N이 홀수일땐 N^2 * (N / 2)^2 짝수일땐 (N-1)^2 * (N / 2)^2 임

[익명(14.39)]

N/2가 어떻게 들어가는거야? 친구말로는 문제가 세번째 for문이 k=i; ~k; k=-1 이라고되어있는데 ~k가 먼지몰라서 k>0일거같다고 해서 그렇다곤하는데... 답지는 O(N^2), O(N^3), O(N^3logN), O(N^4)만있었대..

[익명(183.100)]

시간복잡도 말하는거라면 N^4가 맞음 나누기 2나 -1같은건 걍 무시하기때문에 N^2 * N^2해서 N^4임 k>0이 맞다면

[익명(183.100)]

본문에 적어논거 그대로임 ㅇㅇ 첫번째 for문이 N까지고 두번째 for문이 i*i 즉 i가 N이라고 치면 N^2고 세번째 for문도 k = i 고 i를 N으로 치면 N이 0까지니까 N 다해서 N^4

[익명(14.39)]

의견 고마웡~ !

[익명(175.113)]

주먹구구로 계산하면 진짜 복잡한 상황에서 대처가 안됨. 실제 반복이 몇 번 되는지를 보면 제일 안쪽이 i번, 그걸 바깥쪽에서 i^2번 돌리니까 i^3번이고 i에 대해 다 합치면 (Sum i = 0 to N-1, i^3)임 계산하면 제일 큰 항이 N^4이므로 O(N^4)

[익명(14.39)]

의견 감사요!

[익명(77.103)]

루프 수의 upper bound는 위 댓글대로 하면 되고, lower bound는 i가 n/2 이상인게 n/2개 있으니. 그런 i에 대해서 j는 최소 n^2/4번 돌고 k는 최소 n/2번 도니까 다 합쳐서 적어도 n/2 * n^2/4 * n/2니까 상수*n^4

[익명(14.39)]

i = n j = 최소 n^2/4 k = 최소 n/2 아니에요..!? 음 공부를 좀 더 해봐야겠네요! 의견 감사합니다

[익명(77.103)]

i가 작으면 j와 k의 루프수도 작아서 하한을 예측하기 어려우니까 큰 i에 대해서만 센것임. n/2 이상인 i가 n/2개 있으니까 걔네들에 대해서 j와 k의 루프수를 세주면 j는 i^2번 도니까 최소 n^2/4번 돌고 k는 최소 n/2번 돈다는 말.