java 활용해서 '시간 복잡도' 정리하기!!(개념+코드)

비전공자 신입으로서 일반적인 컴퓨터 공학과 학생만큼의 자료구조라도 공부해야지라는 마음으로

알고리즘에 중심을 두고 공부하고 있다. 

알고리즘하면 자주 나오는 시간 복잡도! '그래서 시간 복잡도란 무엇인가?'라는 생각으로 출발해서 내가 공부도 하면서

블로그에 정리하려고 한다.

혹시 이 포스팅을 보고 피드백을 해주시는 분이 계셨으면 좋겠다!!

일단 개념적으로, '시간 복잡도'란 문제를 해결하는데 걸리는 시간과 입력의 함수 가리킨다. 

컴퓨터 과학에서 알고리즘의 시간 복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다.

(출처: 위키백과)

이런 시간 복잡도를 표현 하는 방식으로 Big-0 표기법을 사용한다.(코드는 java로 설명)

1. O(1) - 상수 시간: 입력값 n이 주어졌을 때, 연산이 1번만 수행된다.

 
public class timeComplexity{
 
    public static void main(String[] args){
 
        int constant = 1; // 시간 복잡도: O(1)
 
    }
}

2. O(log n) - 로그 시간: 입력값 n이 주어졌을 때, 특정한 요건에 따라 필요한 단계가 연산이 줄어 든다.(대표적으로 이진트리검색)

이진트리를 활용해서 푼 알고리즘(클릭)

3. O(n) - 직선적 시간: 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1의 관계를 가진다. (n이 커지는 만큼 정직하게 1대1로 정비례하는 듯)

 
public class timeComplexity{
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int inputNum = sc.nextInt();
        int sum = 0; // 총 합계
        int increment = 1;    // 더해줄 수    
 
        for(int i=0; i<inputNum; i++){ // inputNum이 커질수록 그에 비례해서 합계가 커짐 
            sum += increment;            
        }
    }
}

4. O(n^2) - 2차 시간: 문제를 해결하기 위한 단계의 수는 입력값의 제곱이다.(이중 for문이 있겠다.)

구구단을 이중 for문으로 구현해봤는데, n이 커질수록 문제해결의 단계수는 n^2로 커진다.

 
public class timeComplexity{
 
    public static void main(String[] args){
 
        int n=9;        
        int gugudan=0;
        
        for(int i=1; i<=n; i++){
            
            for(int j=1; j<=n; j++){
                
                gugudan = i*j;
                System.out.println(i+ "*" + j + "=" + gugudan);
            }
        }
    }
}

5. O(C^n) - 지수 시간: 문제를 해결하기 위한 단계의 수는 주어진 상수 C의 n제곱이다.

개념 출처: 조슈아장 블로그

실행시간은?

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) < O(n^n)

오른쪽으로 갈수록 계산 시간은 오래 걸린다!

시간복잡도 간략히 정리 끝.