시간복잡도, Big O, 점근적 표기법

시간 복잡도와 점근적 표기법

 

시간 복잡도 개념

• 시간 복잡도(Time Complexity): 알고리즘이 실행되는 데 걸리는 시간을 나타내는 개념.

• 컴퓨터 성능에 따라 실행 시간이 달라질 수 있으므로, 시간 복잡도를 계산할 때는 “수행에 필요한 단계(Steps)“의 개념을 사용.

• 각 코드 라인의 실행은 고정된 상수 시간(Constant Time)으로 가정.

 

점근적 분석

• 점근적 분석(Asymptotic Analysis)

 임의의 함수가 N->무한대 일 때 어떤 ㅏㅁ수 형태에 근접해지는지 분석

 

• 입력 크기 n이 커질수록 알고리즘의 성능이 어떻게 변하는지 분석(즉,  n->무한대 일 때가 궁금하다)

• 중요하지 않은 낮은 차수나 상수는 제거하여, 입력 크기에 가장 큰 영향을 미치는 최고차항만 고려 (최고차항 계수도 의미없다)

• 예: T(n) = an + b →  T(n) = O(n)

 

시간복잡도

함수의 실행시간을 표현하는 것

주로 점근적 분석을 통해 실행 시간을 단순하게 표현하며 이 때 점근적 표기법으로 표현함

 

lower bound(하한선)

함수 실행 시간은 아무리 빨라도 상수 시간 이상입니다

 

upper bound(상한선)

함수 실행 시간은 아무리 오래 걸려도 N에 비례하는 정도 이하입니다

 

빅세타

상한선과 하한선이 동일한 tight한 bound를 표현할 때 사용

 

 

 

평균

Best 케이스와 Worst 케이스를 제외하고 평균적으로 얼마만큼의 실행시간이 되겠는가. 

Avg는 보통 N/2로 계산함. 오메가로 표현하긴 애매하다. 확실한 Big-O 표기법으로만 표현

 

성능순서

O(1) < O(logN) < O(N) < O(N*logN) < O(N^2) < O(2^N) < O(N!)

 

 

빅-오 표기법이 많이 사용되는 이유

1. 최악의 경우를 다루기 때문에 실용적.

2. 다른 바운드()를 계산하기 복잡.

3. 표준화된 방식으로 문서와 자료에서 많이 사용.

 

 

코드 예제 1: 배열 곱셈

int* multiplyArray(int* arr, int size, int multiplier) {
    int* result = new int[size];
    
    for (int i = 0; i < size; ++i) {
        result[i] = arr[i] * multiplier;
    }
    return result;
}

 

코드 예제 2: 배열에서 값 찾기

bool findTarget(int* arr, int size, int target) {
    for (int i = 0; i < size; ++i) {
        if (arr[i] == target) return true;
    }
    return false;
}

 

 

코드 예제 3: 이중 루프

for (int i = 0; i < size; ++i) {
    for (int j = 0; j < size; ++j) {
        // 작업
    }
}

 

 

 

 

코드 예제 4: 바이너리 서치

int binarySearch(int* arr, int size, int target) {
    int left = 0, right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

(N/2^k) = 1  <=> k = logn

 

 

결론

• 시간 복잡도는 알고리즘의 효율성을 평가하는 중요한 도구.

• 점근적 표기법을 통해 입력 크기에 따른 실행 시간을 간단히 표현.

• 빅-오 표기법은 실용성과 단순성 때문에 가장 많이 사용됨.

 

 

 

https://www.youtube.com/watch?v=aL0XXc1yGPs&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe