• 1. 명령 수행수와 실제 시간의 관계
• 2. 실제 수행시간을 어림짐작하기
• 3. O(n제곱) 의 비효율성

이전 글에서 시간 복잡도가 무엇인지, 어떤식으로 계산하는지 알아봤다.

이제 그 계산해서 나온 시간 복잡도의 값은 실제로 어느정도의 시간을 뜻하는 것인지 알아보자.

1. 명령 수행수와 실제 시간의 관계

• 아무리 컴퓨터가 빠른 계산 속도를 자랑한들, 명령 수행 횟수가 많아질수록 수행 시간은 늘어날 수밖에 없다.

• 그리고 같은 횟수의 명령 처리를 하더라도, 컴퓨터의 사양에 따라서 처리 속도가 전부 다 다르다.

  • 그래서 실제 수행시간을 구할 땐, 평균적인 사양으로 모든 컴퓨터를 묶어서 보수적으로 바라볼 필요가 있다.

2. 실제 수행시간을 어림짐작하기

• 보통 연산 1억번 즉, O(1억) 이 1초 가 걸린다고 한다.

  • 물론 1억 == 1초 가 정확한 공식은 아니다.

    • 이유 1 : 시대가 지나면서 하드웨어의 성능이 좋아지기 때문에 실제론 훨씬 더 빠를 수 있다.

    • 이유 2 : 아주 단순한 연산을 반복한다면, 1억번에 1초가 걸리는 속도보다 훨씬 빠르다.

      • class Scratch {
            public static void main(String[] args) {
                long beforeTime1 = System.currentTimeMillis();
                
                long sum1 = 0;
                for (long i = 0; i < 100_000_000L; i++) {
                    sum1 += i * i;
                }
                    
                long afterTime1 = System.currentTimeMillis();
                long secDiffTime1 = (afterTime1 - beforeTime1) / 1000;
                System.out.println("시간차이 : "+secDiffTime1 + " 초");
            }
        }
                
        // 출력 결과
        // 시간차이 : 0 초
        

        • 이렇듯 ‘곱셈 + 누적합 대입 연산’ 을 반복 수행하는 경우, 1억번을 수행해도 실제 수행 시간은 1초 미만이 나온다.
          • 그래서 1초가 걸리는 횟수는 몇번인지 계속해서 횟수를 늘려보며 찾아보았다.

      • class Scratch {
            public static void main(String[] args) {
                long beforeTime1 = System.currentTimeMillis();
                
                long sum1 = 0;
                for (long i = 0; i < 1_800_000_000L; i++) {
                    sum1 += i * i;
                }
                    
                long afterTime1 = System.currentTimeMillis();
                long secDiffTime1 = (afterTime1 - beforeTime1) / 1000;
                System.out.println("시간차이 : "+secDiffTime1 + " 초");
            }
        }
                
        // 출력 결과
        // 시간차이 : 1 초
        

        • 놀랍게도 17억번까지는 1초 미만이고 18억번을 반복해야 1초가 나온다.

• 그렇다면 왜 1억번에 1초라고 하는 것일까??

  1. 이전 글에서도 봤다시피, 시간 복잡도는 최악을 가정하고 산정한다.

     • 그리고 알고리즘 문제를 풀 때와 프로그래밍을 할 땐, 보통 저렇게 단순한 연산만이 아닌 복잡한 연산을 반복하는 경우도 있을 것이다.

  2. 하드웨어의 속도는 아주 천천히 증가한다.

  3. 어차피 이 법칙 자체가 근사값이기 때문에 1억이란 기준은 현재까지는 유효하다고 느낀다.

• 위와 같은 이유들로 O(1억) == 1초 가 나온 것이다.

  • 최상, 최악 상관없이 어느 상황에서든지 프로그램이 잘 돌아가야 하기때문에 이러한 보수적인 스탠스는 굉장히 바람직하다고 생각한다.

3. O(n제곱) 의 비효율성

• 1억번 == 1초가 성립될 때, 알고리즘 문제에서 제한시간이 1초라고 가정해보자.

• 각 시간복잡도에 따른 명령 수행 가능 횟수

  • O(logN) : 1억

  • O(N) : 1억

  • O(nLogN): 5백만

  • O(N^2) : 1만

  • O(N^3) : 500

  • O(2^N) : 20

  • O(N!): 10

• 위에서 보이듯이, O(n제곱) 부터 효율성이 급격히 떨어지는 모습을 볼 수 있다.

  • 이 비효율성은 명령 수행 횟수의 단위가 커지면 커질수록 더욱 현격하게 드러난다.
    • 그래서 O(n제곱) 의 시간복잡도를 가지는 선택, 삽입, 버블 정렬 등은 거의 쓰이지 않는다.
    • 단위가 조금만 커져도 보통 시간초과가 되기 때문이다.
    • 실제로 Arrays.sort(), Collections.sort() 같은 정렬 메서드들은 O(n log n) 의 정렬 알고리즘을 사용한다.
      • 보통 ‘병합 정렬’과 ‘삽입 정렬’의 장점들만 뽑아서 만든 하이브리드 정렬인 팀 정렬 (Tim sort) 을 사용한다.