시간 복잡도

시간 복잡도 

 : 입력 크기의 값에 대해 단위 연산을 몇번 수행하는지 계산하여, 알고리즘의 수행 시간을 평가하는 방법

 

3가지 점근적  표현

 O (빅오): 최악의 상황을 고려하여 성능 특정 결과 표현  

 Θ (세타) : 평균적인 경우에서의 성능 측정 결과 표현

 Ω(오메가) : 최선의 상황일때 의 성능 특정 결과 표현

 

 

 

Big-O Complexity Chart

https://www.bigocheatsheet.com

Big-O 복잡도를 표기할 때 알고리즘별로 속도를 표기한 차트입니다. 요소들이 증가해도 빠른게 O(log n), O(1)이고 제일 느린게 O(nl)입니다. 

 

빅오 표기법 예제 - 1

function big_o(n) {
	let sum = 0; // 1회
    sum =  n * 2; // 1회
    return sum; // 1회
}

 

총 3회 라인 코드가 실행되고 아무리 커지도라도 상수이니깐 O(1)로 표기하면 됩니다. 즉, 코드들만 실행할 때는 O(1)으로 생각하면 됩니다.

 

 

빅오 표기법 예제 - 2

function big_o(arr, n) {
	let sum = 0; // 1회
    for(let i = 0; i < n; i++){
    	sum += arr[i]; // n회
    } 
    return sum; // 1회
}

 

n+2회가 실행되며 반복문이 실행되기 때문에 O(N)이 됩니다.

 

 

빅오 표기법 예제 - 3

function big_o(arr, n) {
	let sum = 0; // 1회
    for(let i = 0; i < n; i++){
    	for(let j =0; j < n; j++{
        	sum +=arr[i][j]; // n * n = n의 2제곱
        }
    } 
    return sum; // 1회
}

 

반복문이 중첩이 되어 n의 2제곱이 실행되기 때문에 n의 제곱  + 2가 돼서 O(n의 2제곱)이 됩니다. 

만약에 O(n의 2제곱 + n + 2)일때도 O(N의 2제곱)이 됩니다.

 

 

빅오 표기법 예제 - 4

function big_o(n) {
	let sum = 0; // 1회
    fot(let i = 0; i < n; i *= 2){
        	sum +=2; // n / 2회
    } 
    return sum; // 1회
}

 

머지 스트와 분활 정복할 때 사용하는 방법으로 n / 2 + 2 ->O(log N)이 됩니다.

 

머지스트란 비교정렬이 낼 수 있는 가장 높은 겅능의 시간 복잡도인 O에 도달한 정렬 알고리즘 중 하나입니다. 큰 문제들을 작은 문제들로 나워서 해결한 뒤, 해결된 작은 문제들로 큰 문제를 해결하는 분할 정복에 기초한 알고리즘입니다.

시간 복잡도를 잘 생각하면서 코드를 짜야합니다.