자료구조 - 알고리즘 성능 분석(빅오표기법)

알고리즘의 성능 분석은 컴퓨터 과학에서 매우 중요한 주제입니다. 성능 분석을 통해 알고리즘의 효율성을 평가하고, 최적화를 통해 성능을 향상시킬 수 있습니다.

 

성능 분석은 다양한 방법이 있고 빅오 표기법(Big-O Notation)을 주로 사용하여 표현합니다.

 

[빅오 표기법]

빅오 표기법(Big-O Notation)은 알고리즘의 성능을 평가할 때, 특히 시간 복잡도와 공간 복잡도를 표현하는 데 사용되는 수학적 표기법입니다. 빅오 표기법은 알고리즘이 실행되는 시간이나 사용되는 메모리 양을 입력 크기(n)의 함수로 나타냅니다. 이 표기법은 최악의 경우 성능을 기준으로 알고리즘의 효율성을 비교하는 데 유용합니다.

 

다음으로 많이 쓰이는 빅오 표기법을 수행시간의 순서대로 알아보겠습니다.

1. 상수 시간 (O(1)): 알고리즘이 입력 크기와 상관없이 항상 일정한 시간 내에 실행됩니다.
2. 로그 시간 (O(log n)): 알고리즘의 실행 시간이 입력 크기의 로그에 비례합니다.
3. 선형 시간 (O(n)): 알고리즘의 실행 시간이 입력 크기에 비례합니다.
4. 선형 로그 시간 (O(n log n)): 알고리즘의 실행 시간이 입력 크기와 로그 값의 곱에 비례합니다.
5. 제곱 시간 (O(n^2)): 알고리즘의 실행 시간이 입력 크기의 제곱에 비례합니다.
6. 지수 시간 (O(2^n)): 알고리즘의 실행 시간이 입력 크기에 대한 지수 함수에 비례합니다.

 

[빅오 표기법의 특징]

• 최악의 경우: 빅오 표기법은 최악의 경우 성능을 나타냅니다. 예를 들어, 선형 탐색의 최악의 경우는 찾고자 하는 요소가 마지막에 있을 때입니다.
• 상수 생략: 빅오 표기법에서는 상수를 무시합니다. 예를 들어, O(2n)은 O(n)으로 표현됩니다.
• 높은 차수의 항만 고려: 빅오 표기법에서는 가장 높은 차수의 항만 고려합니다. 예를 들어, O(n^2 + n)은 O(n^2)로 표현됩니다.

 

빅오 표기법을 사용하여 시간 복잡도와 공간 복잡도를 표현합니다.

 

 

[시간 복잡도]

시간 복잡도는 알고리즘이 입력 크기에 따라 실행 시간을 얼마나 소비하는지를 분석합니다.

시간 복잡도에 대한 예시를 하나 보겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>

int find_max(const std::vector<int>& arr) 
{
    int max_value = arr[0];
    for (int num : arr) 
    {
        if (num > max_value)
        {
            max_value = num;
        }
    }
    return max_value;
}

int main() 
{
    std::vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    std::cout << "최대값: " << find_max(arr) << std::endl;
    return 0;
}

 

 

 

 

[공간 복잡도]

공간 복잡도는 알고리즘이 실행될 때 필요한 메모리 공간의 양을 분석합니다.

#include <iostream>
#include <vector>

std::vector<int> copy_list(const std::vector<int>& arr) 
{
    std::vector<int> new_arr;
    for (int item : arr) 
    {
        new_arr.push_back(item);
    }
    return new_arr;
}

int main() 
{
    std::vector<int> arr = {1, 2, 3, 4, 5};
    std::vector<int> copied_arr = copy_list(arr);
    std::cout << "복사된 리스트: ";
    for (int item : copied_arr) 
    {
        std::cout << item << " ";
    }
    std::cout << std::endl;
    return 0;
}