Nested Loop면 무조건 Big O가 O(n^2)임?

[익명(114.202)]

ㅈㄱㄴ

[익명(211.209)]

2중포문 n^2, 3중포문 n^3

[익명(211.209)]

어떻게 조회하냐에 따라 지수배로 늘어가기도 하고

[익명(114.202)]

그냥 무조건 이중포문 삼중포문은 빅오가 n^2랑 n^3임?

[익명(114.202)]

조건은 상수라 제외하잖어

[익명(211.209)]

그건 아니고.. 만약 주어진 input이 n개인데 그 n개를 n^2번 도는지 n^3돌아야 하는지를 물어보는거야 빅오노테이션은

[익명(211.209)]

n이 1,2,3,4,5라고할때 1,2,3,4,5 로 순회하면 n이고 1234512345123451234512345 순회하는 방향이면 n^2이고 123451234512345123.... n^3

[익명(211.209)]

보통 알고리즘 평가하라고 할 때는 n이 딱 주어지지 않잖아. 어떤 인풋이 들어올지 어케알아. 그러니 n이라고 일반화 시켜서 평가하는거임.

[익명(114.202)]

이해했다 이기야

[익명(211.209)]

만약 님 조건문이 어떤 상황에서도 2중포문으로 돌지않고 1중포문으로 돈다 (loop invariants). 그럼 O(n)이지

[익명(114.202)]

그럼 Big O 에선 무조건 항이 큰 쪽을 기준으로 하고 나머진 절삭해서 버리면 됌?

[익명(211.209)]

ㅇㅇ 왜냐면 n이 준나게 커지면 큰항만 의미 있거든. 그래프 그려보면 됨 n^3+n^2하고 n^3 그래프를 그려봐. 거의 모양이 비슷해 (물론 n의 값이 작은 경우에는 의미있을 수 있지만, 요즘 연산속도로 그정도 오차는 무의미하다고 생각해도 될듯)

[익명(211.209)]

https://www.wolframalpha.com/input?i=graph+n%5E3+%2B+n%5E2+from+n+%3D+1+to+n+%3D+100000
n^3
+ n^2

[익명(211.209)]

https://www.wolframalpha.com/input?i=graph+n%5E3+from+n+%3D+1+to+n+%3D+100000
n^3

[익명(114.202)]

알겠더 이거야

[익명(211.209)]

반면에 n^2은 y축이 올라가는게 확실히 적은게 보임.
https://www.wolframalpha.com/input?i=graph+n%5E2+from+n+%3D+1+to+n+%3D+100000
CPU연산
횟수가 그정도로 그만큼 줄어든다는 의미이니 유의미함.
지금 계산기에 떄린 바운드는 n=10000으로 했지만, 보통 n이 수십, 수억, 수천억 이렇게 나오는게 허다하니..

[익명(chartman)]

무조건이라곤 못함 nlogn도 for문으로 쓰면 2중 for문일테니