🤍 알고리즘 - 빅오 표기법 정리

7) 알고리즘 - 빅오 표기법 정리

• 빅오(Big-O)

  • 알고리즘의 성능을 수학적으로 표기해주는 표기법

  • 알고리즘의 시간, 공간 복잡도를 표현할 수 있음

  • 알고리즘의 실제 running time을 표시하는 것이라고 하기보다는 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표이기 때문에 상수와 같은 숫자들은 모두 1이된다.

• O(1) 알고리즘

    public boolean F(int[] n) {
        return (n[0] == 0) ? true : false;
    }
  

  • 입력 데이터의 크기에 상관 없이 언제나 일정한 시간이 걸리는 알고리즘.

  • 함수를 보면 첫 번째 배열 방의 값이 0인지를 확인한다. 인자로 받는 배열 방의 값이 얼마나 큰지 상관 없이 언제나 일정한 속도로 결과를 반환한다.

  

  • 예를 들어 가로축이 데이터의 크기이고 세로축을 처리 시간이라고 할 때 데이터가 증가함에 따라 성능의 변화가 없다.

• O(n) 알고리즘

    public void F(int[] n) {
        for (int i = 0; i < n.length; i++) {
            System.out.println(i);
        }
    }
  

  • 입력 데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘을 표현할 때 사용.

  • 함수는 n개의 데이터를 받으면 n번 루프를 도니까 n이 한번 늘어날 때마다 처리가 한번 씩 늘어나서 n의 크기만큼 처리시간이 걸리게 된다.

  

  • 데이터가 증가함에 따라 비례해서 처리 시간도 같이 증가하게 된다.

  • 언제나 데이터와 시간이 같은 비율로 증가하기 때문에 그래프는 직선으로 표현된다.

• O(n²) 알고리즘

    public void F(int[] n) {
        for (int i = 0; i < n.length; i++) {
            for (int j = 0; j < n.length; j++) {
                System.out.println(i + j);
            }
        }
    }
  

  • n을 돌리면서 그 안에서 n으로 루프를 또 돌릴 때, n²이 된다.

  • 그래서 n개의 데이터를 받으면 첫 번째 루프에서 n번 돌면서 각각의 element에서 n번씩 또 도니까 처리 횟수가 n을 가로 세로 길이로 가지는 면적만큼 되는 것이다.

  

  • 따라서 n이 한 번 늘어날 때마다 아래 한 줄, 오른쪽 한 줄(행, 열) n만큼씩 또 붙으니까 데이터가 커지면 커질 수록 처리 시간에 부담도 커진다.

  

  • 처음에는 조금씩 상승하다가 나중에는 수직 상승된다.

• O(nm) 알고리즘

    public void F(int[] n, int[] m) {
        for (int i = 0; i < n.length; i++) {
            for (int j = 0; j < m.length; j++) {
                System.out.println(i + j);
            }
        }
    }
  

  • n을 두 번 돌리는 게 아니라 n을 m만큼 돌리는 것이다.

  

  • n은 엄청 크고 m은 엄청 작을 수도 있기 때문에 변수가 다르다면 빅오 표기법에도 다르게 표시를 해야된다!

  • 그래프는 O(n²)와 마찬가지로 데이터가 증가할 수록 수직에 가까운 기울기가 된다.

• O(n³) 알고리즘

    public void F(int[] n) {
        for (int i = 0; i < n.length; i++) {
            for (int j = 0; j < n.length; j++) {
                for (int k = 0; k < n.length; k++) {
                    System.out.println(i + j + k);
                }
            }
        }
    }
  

  • 루프를 n을 가지고 3중으로 돌리면 n³이 된다.

  

  

  • 데이터가 늘어남에 따라 가로, 세로, 높이까지 늘기 때문에 아무래도 O(n²)보다 더 급격하게 수직 상승하는 그래프가 된다.

• O(2ⁿ) 알고리즘

  • 피보나치(Fibonacci) 수열

  

  • 한 면을 기준으로 정사각형을 만든다. 처음은 1일 것. 그렇다면 그 후에 1이 2개가 붙어서 직사각형이 된다. 그러면 가로가 2일 것이고 그걸 기준으로 정사각형을 만든다.

  • 그러면 늘어난 면이 3이 된다. 또 이 면을 기준으로 정사각형을 만든다. 그러면 직사각형으로 된 한 면이 5가 된다. 그러면 그 면을 기준으로 정사각형을 만든다. 그러면 8이 되고 .. 1 -> 2 -> 3 -> 5 ->8 -> 13 -> 21 -> 34 -> 55 이런식으로 기하학의 황금비율인 피보나치의 나선형이 만들어지게 된다.

  • 수학적으로 접근하면 1-> 1-> 2-> 3 -> 5 -> 8 -> 13 -> 21 -> 34 -> 55 이 부분은

  • 1을 두 번 더해서 2가 되고 1+2 = 3, 3+5 = 8, 3+5 = 8 ··· 21+34 = 55가 된다.

  • 피노차리를 구하는 방법을 재귀함수를 이용해서 풀면

    public int F(int n, int[] r) {
        if (n <= 0) {
            return 0;
        } else if (n == 1) {
            r[n] = 1;
            return r[n];
        }
        r[n] = F(n - 1, r) + F(n - 2, r);
        return r[n];
    }
  

  • 함수를 호출할 때마다 바로 전의 숫자와 전전 숫자를 알아야 더할 수 있기 때문에 해당 숫자를 알아내기 위해서 하나 뺀 숫자를 가지고 재귀호출을 하고, 그 다음 두 번 뺀 숫자를 가지고 재귀호출을 한다.

  

  • 이렇게 매번 함수가 호출될 때마다 2번씩 또 호출을 하는데 그걸 트리의 높이만큼 반복하는 것이다.

  

• 그래프로 보면 데이터의 증가량에 따라 처리 시간이 급격하게 증가하는 것을 확인할 수 있다. 앞서 살펴본 O(n²)이나 O(n³)보다 훨씬 수직 상승되어있다.

• O(log n) 알고리즘

  • 대표적인 알고리즘은 이진 검색(이진 탐색)이다.

  

  • 이진 검색을 하려면 우선 가운데 값을 찾아서 key값(지금 구하려는 수)과 비교를 한다.

  • 2<7이므로 뒷 부분은 버리고 앞 부분만 탐색한다.

  • 가운데 값이 3을 가지고 비교한다. 2<3 이므로 앞 부분만 다시 탐색한다.

  • 2>1 이므로 다시 탐색하고 더 이상 남은 항목이 없으므로 탐색 실패.

  • 이렇게 한 번 처리가 진행될 때마다 검색해야 하는 데이터의 양이 절반씩 뚝 뚝 떨어지는 것을 O(log n) 알고리즘이라고 한다.

    public int F(int k, int[] arr, int s, int e) {
        if (s > e) {
            return -1;
        }
      
        int m = (s + e) / 2;
      
        if (arr[m] == k) {
            return m;
        } else if (arr[m] > k) {
            return F(k, arr, s, m - 1);
        } else {
            return F(k, arr, m + 1, e);
        }
    }
  
  

  • 처음 호출 될 때는 시작 부분은 0, 끝 점은 배열의 맨 마지막 방이 된다.

  • int m = (s + e) / 2; 주어진 range에 중간값을 찾는다.

  • 찾는 값이 중간 값보다 작으면 중간 지점 바로 전 까지 range를 조정해서 다시 호출하고 중간 값보다 크면 중간 지점 다음 방부터 range를 조정해서 다시 호출한다.

  • 이렇게 하면 한 번 함수가 호출될 때마다 중값값을 기준으로 절반은 검색 영역에서 제외시켜 버리기 때문에 순차 검색에 비교해서 속도가 현저하게 빠르다.

  

• O(log n)이 O(n)보다도 훨씬 적게 든다. 데이터가 증가해도 성능이 크게 차이나지 않는다.

• 📌 중요한 부분

  • 빅오 표기법에서 상수는 과감하게 버린다!

    public void F(int[] n) {
    // 첫 번째 for 루프
        for (int i = 0; i < n.length; i++) {
            System.out.println(i);
        }
      
    // 두 번째 for 루프
        for (int i = 0; i < n.length; i++) {
            System.out.println(i);
            }
        }
  

  • 해당 코드는 시간 복잡도가 얼마일까? 이건 n만큼씩 2번 돌리니까 2n만큼의 시간이 걸린다. 그런데 빅오 표기법에서는 O(2n)은 그냥 O(n)으로 표시한다!

  • 왜냐하면 빅오 표기법은 실제 알고리즘의 running time을 측정하기 위해 만든 게 아니라 장기적으로 데이터가 증가함에 따라 처리 시간에 증가율을 예측하기 위해 만들어진 표기법이기 때문이다. 상수는 고정된 숫자이므로 증가율에 영향을 주지않는다.

  • 마찬가지로 O(n²+ n²) 도 O(n²)로 표기한다.