개념 정리 : 시간복잡도 정리

밀라 알고리즘 스터디 2주차 개념 정리 

 

시간복잡도 

: 입력값과 연산 수행시간의 상관관계를 나타내는 척도

최상의 경우 - 오메가 표기법
평균의 경우 - 세타 표기법
최악의 경우 - 빅오 표기법
=> 시간복잡도는 최악을 기준으로 빅오 표기법으로 판단하여 성능 예측

 

빅오표기법
 - 시간 복잡도 : 입력된 N의 크기에 따라 실행되는 조작의 수
 - 공간 복잡도 : 알고리즘이 실행될 때 사용하는 메모리의 양
   ( 메모리의 발전으로 공간 복잡도의 중요성이 많이 줄어들었음)

 

1) O(1) 
예제 코드 

const sum = (N+1) * N /2

 

2) O(log n)
예제 코드 

funtion func(n){
 let i = 1;
 while(i<n){
  console.log(i);
  i = i*2;
 }
}

3) O(n) 
예제 코드

let sum = 0;
for(let i = 0; i<=N; i++){
 sum += i ; 
}

3) O(nlogn)

입력의 절반으로 나눌때마다 각 부분을 독립적으로 처리 
ex. 병합정렬, 퀵정렬, 힙정렬

4) O(n^2) 
알고리즘이 실행시간이 입력 크기의 제곱에 비례 , 각 원소를 다른 모든 원소와 비교하는 경우
ex. 버블 정렬, 선택 정렬, 삽입 정렬

function func(n){
 for(let i = 0 ; i < n.length; i++){
  for(let j = 0 ; j < n.length; j++){
   console.log(i,j);
  }
 }
}