크기가 n인 배열 a[n]에 대한 다음 프로그램의 시간복잡도로 맞는 것을 모두 고르시오 ... 답: 3,4 1. O(1) 2. O(n) 3. O(n^2) 4. O(n^3)
for (int i = 0; i < n; ++i) {
for (int j = i+1; j <n; ++ i) {
swap(a+i, a+j) // O(1)
}
}
for (int i = 0; i < n; ++i) {
for (int j = i+1; j <n; ++ i) {
swap(a+i, a+j) // O(1)
}
}
여기서 for문이 두개 나왔으니 n*(n+1)되서 O(n^2)가 되는건 알겠는데
O(n^3)은 어떻게 해서 답이 된건가요????
swap함수는 그냥 O(1)일거라고 저는 생각했거든요
빅오 세타 오메가 의미는 아시나요??? 빅오는 해당 크기보다 작거나 같은 모든 집합이에요
O(n^3)이면 3n^3 2n^2+1 2n 1 nlogn logn 등등 다 포함하는 집합과ㅣㄴ계
점근적 상한이라고 하죠
그래서 3번 4번인거에요
그리고 n(n+1)이라 n^2이 아니에요. 저거 보면 두번째 루프가 1+2 + 3+ 4+n-1 증가하는데 빅오는 최악의 경우를 가정하고 측정해요. 그래서 모든 알고리즘이 빅오 기준이구요.
토를 달자면 저 루프는 n(n+1) / 2 야.
저거 그대로 문제로 나왔으면 시비 걸어서 전원 맞게 할 수도 있겠다. for(int j....) 마지막에 ++j가 아니라 ++i로 미스 타이핑. 결론은 무한루프.