[알고리즘] 효율성

알고리즘에서 효율성은 경진 프로그래밍의 핵심이다.

• 빅오 표기법 (Big-O Notation) : 입력에 대한 최고차항의 상수항을 제거한 표기법 ( ex. 3n^2+2n = O(n^2) )
• 시간복잡도 : 시간복잡도는 입력에 대해 알고리즘이 얼마만큼의 시간을 사용할지를 근사적으로 알려준다.
  1. O(1) : 상수 시간 알고리즘으로 수행시간은 입력의 크기에 영향을 받지 않는다.

      cin>>n;
      int a = n;
      int b = 2;
      cout<<a+b<<endl;

     위와 같은 코드는 입력이 어떤 값이 들어와도 시간 복잡도에 영향이 없다.
  2. O(n) : 선형 시간 알고리즘으로 입력을 쭉 살펴보는 과정을 상수 번 수행한다.

      for(int i=0; i<n; i++) {
      //비지니스 로직
      }

     위와 같은 코드는 입력 n만큼 선회하며 확인하게 된다.
  3. O(n^2) : 제곱 시간 알고리즘으로 보통 2중으로 중첩된 반목문을 사용한다.
     

     for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
        //비지니스 로직
        }
     }

  4. O(log n) : 로그 시간 알고리즘으로 대체로 단계마다 입력의 크기를 절반씩 줄여나가는 것으로 입력의 크기가 증가해도 수행 시간에 크게 영향이 없다.
  5. O(2^n) : 이 시간 복잡도는 입력 원소로 만들 수 있는 모든 부분집합을 한 번씩 살펴보고는 알고리즘의 시간 복잡도를 기술할 때 자주 사용된다.

      {1,2,3}의 모든 부분집합 => {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

  6. O(n!) : 이 시간 복잡도는 입력 원소로 만들 수 있는 모든 순열을 한 번씩 살펴보는 알고리즘의 시간 복잡도를 기술할 때 자줏 사용된다.

      {1,2,3}의 모든 수열 => {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}

• 이와 같이 알고리즘의 시간 복잡도를 알고 있으면 역으로 입력에 대한 적당한 알고리즘의 시간복잡도를 유추해 볼 수 있다.