알고리즘 시간 복잡도 (Time Complexity)

시간 복잡도 (Time Complexity)

입력 크기와 알고리즘간의 관계
알고리즘의 복잡도를 나타내는 지표 중 하나
프로그램의 동작시간을 가늠해 볼 수 있는 수단

 

Big-O 표기법 (O(n))

일반적으로 가장 많이 사용함
가장 최악의 상황을 포함한 시간의 상한선

 

시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문

입력의 크기가 커지면 반복문이 수행 시간을 지배함

가장 높은 차수로 표기

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

 

// 무조건 상수회 실행 : O(1)
if(n > 10) {
    System.out.println(n);
}


// n번, n + 10, 3n + 10번 등 실행 : O(n)
for(int num = 0; num < 3; num++) {    // 이중 반복문이지만 상위는 상수로 반복, 3n 실행
    for(int index = 0; index < n; index++) {
        System.out.println(index);
    }
}


// n^2, n^2 + 1000, 100n^2 - 100, 300n^2 + 1번 등 실행 : (O(n^2))
for(int i = 0; i < 3; i++) {    // 삼중 반복문이지만 상위는 상수로 반복, 3n^2 실행
    for(int num = 0; num < n; num++) {
        for(int index = 0; index < n; index++) {
            System.out.println(index);
        }
    }
}


// 1부터 n까지의 합 (O(n)) - 1
//입력 n에 따라 덧셈을 n번 해야함
int sum = 0;
for(int i = 1; i <= n; i++) {
    sum += i;
}    


// 1부터 n까지의 합 (O(1)) - 2
// 반복문이 없음
(n(n + 1) / 2)

 

 

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스