제가 지금 해결하는 알고리즘을 최적화중에 있는데요
시간복잡도가 O(n^2) 라고 할때
보통 간단한 예로
0에서 n을 거치는 2중 for 루프가 있잖아요?
for(i){
//i는 0부터 n까지 거쳐간다
for(j){
//j도 역시 0부터 n까지 거쳐간다
}
}
이런식..
그런데 여기서 궁금한게 있습니다.
일단i는 0에서 n까지 무조건 거쳐간다 치고
즉,
for(i){
//i는 0부터 n까지 거쳐간다.
}
이 있고 루프 안에 또 for루프를 넣는대신
랜덤한 개수의 일을 수행을 합니다.
랜덤한 수는 0부터 n까지 수의 사이구요, 매번 iterate때 마다 다를수 있고 같을수있고 말그대로 알수없습니다.
만약 j개의 일을 수행한다하면 j의 각각 하나당 수행시간은 O(1)입니다.
즉,
for(i){
//i는 0부터 n까지 거쳐간다.
//여기서 서는 j개수의 일을 한다. 각각 1개의 일은 O(1)의 시간을 갖는다. j는 0개가 될수도있고 n개가 될수도있다.
}
이렇게 했을때 이것은 O(n^2)인가요? O(n)인가요?
최악의 경우 j가 전부 n이면 O(n^2)이고
아니면 O(n + n + n + n +... + n) 이되서 결국 O(n)일까요?
아니면 둘다 아닌가요...
