[알고리즘 -1] 시간복잡도, 빅오표기법, 공간복잡도

 

 

알고리즘 문제를 풀 때 예제 입출력이 맞게 나와도 실제 코드를 제출했을 때 시간초과로 통과하지 못하는 경우가 종종 있다. 우리가 작성한 코드의 실행 시간을 어떻게 알 수 있을까?

 

이러한 시간은 사용된 언어 종류, 컴퓨터 사양, 컴파일러 속도 등 여러가지 영향을 받게 된다. 따라서 시간복잡도를 설명할 때는 입력값과 연산 수행 시간의 상관관계를  중점으로 설명한다  

 

시간복잡도 (time complexity)

입력크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간, 주요로직의 반복 횟수를 중점으로 측정됨

 

입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘

 

 

 

시간복잡도 표현방법은 3가지가 있다

 

1) 오메가 표기법 (Big-Ω) : 최상의 경우

2) 세타 표기법 (Big-θ) : 평균의 경우

3) 빅오 표기법 (Big-O) : 최악의 경우

 

시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다

 

 

 

 

빅오표기법 (Big-O)

복잡도에서 가장 영향을 많이 끼치는 항의 상수인자 빼고 나머지 항을 없애서 복잡도를 나타냄

즉, 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 하도록 하는 것이다.

다음과 같은 시간복잡도 일때 가장 많은 영향을 끼지는 항인 n^2만 신경쓴다

 

 

 

n! > 2 ^ n > n ^2 > nlogn > n > logn > 1 순

 

 

예제 코드를 통해 빅오표기법으로 표현해보면

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int a = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                a += i + j;
            }
        }
        System.out.println(a);
    }
}

 

위와 같이 반복문이 두 번 있는 케이스는 시간복잡도가 O(n^2)이다.

 

 

 

자료구조의 시간복잡도

 

 

 

문제를 보고 로직을 생각할 때 시간복잡도를 대략 계산하고, 또한 로직에 알맞는 자료구조를 선택할 때  낮은 시간복잡도를 가진 자료구조를 생각하는 연습이 필요하다

 

 

 

공간복잡도 

입력크기에 대해 어떠한 알고리즘이 실행되는 데 필요한 메모리 공간

 

총 공간 요구 = 고정 공간 요구 + 가변 공간 요구

 

- 고정 공간 : 코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수를 말한다

- 가변 공간 : 동적으로 필요한 공간을 말한다

 

공간복잡도 계산은 시간복잡도와 비슷하게 빅 오 표기법으로 표현한다

public int factorial(int n){
    if(n==1){
            return n;
    }
    return n*factorial(n-1);
}

 

다음 코드는 재귀함수로 구현한 것이며, 변수 n이 n개 만들어진다 따라서 공간 복잡도는 O(n) 이다