[자료구조] 복잡도 - 시간 복잡도 / 공간 복잡도

자료구조는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 말한다.

 

- 시간 복잡도

문제를 해결하는데 걸리는 시간과 입력의 함수 관계

알고리즘 로직이 얼마나 오랜 시간 걸리는지를 나타내는데 쓰인다. -> 빅오 표기법으로 나타냄

 

    for(int i = 0; i < 10; i++){
        for(int i = 0; j < n; j++){
            for(int k = 0; k < n ; k++){
                if(true) cout << k << '\n';
            }
        }
    }
    
    for(int i = 0; i < n ; i++){
        if (true) cout << i << '\n';
    }

->  시간 복잡도는 10n^2 + n

-> 빅오 표기법은 O(n^2)

 

빅오 표기법

빅오 표기법은 입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타냄

가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없애는 것 ex ) 10n^2 + n  -> n^2

 

시간 복잡도의 존재 이유

 

시간 복잡도는 효율적인 코드로 개선하는데 쓰이는 척도가 됨

 O(1) 과 O(n) 은 크기가 커질수록 차이가 많이 난다.

 

- 공간 복잡도

공간복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양

정적 변수로 선언된 것 말고 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함

 

int a[1004];   //a 배열은 1004*4 바이트의 크기를 가지게 됨

 

- 자료 구조에서의 시간 복잡도

보통 시간 복잡도를 생각 할 때 평균, 그리고 최악의 시간 복잡도를 고려함

 

자료 구조의 평균 시간 복잡도

자료 구조의 평균 시간 복잡도

자료 구조 최악의 시간 복잡도

자료 구조 최악의 시간 복잡도