CS(Computer Science)/알고리즘

알고리즘 성능분석

galid1 2018. 10. 21. 15:08
728x90


1. 공간복잡도 

- 알고리즘에 사용되는 메모리 공간의 총량

- 메모리 사용량의 분석결과




2. 시간복잡도 

- 알고리즘에 사용되는 연산횟수의 총량

- 속도에 대한 분석결과

- 연산의 횟수를 센다


1. n번 반복 

1
2
3
for(int i = 0; i < n; i++){
    // code
}
cs

시간 복잡도 : O(n)


2. n/2 번 반복

1
2
3
for(int i = 0; i < n; i += 2){
    // code
}
cs

시간 복잡도 : O(n/2)


3. logN (밑 =2)

1
2
3
for(int i = 0; i < n; i *= 2){
    // code
}
cs

시간 복잡도 : O(logN (밑=2))


4. N^n

1
2
3
4
5
for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        // code
    }
}
cs
시간 복잡도 : O(n^2)


*보통은 공간복잡도 보다 시간복잡도에 초점을 맞춘다.