[자료구조] Big-O(빅오) 표기법

Big-O표기법 : 알고리즘의 성능을 수학적으로 표현해주는 표기법

시간/공간복잡도 표현가능

알고리즘의 실제 러닝타임을 표시하기보단 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표

 

O(1) : 입력데이터가 증가함에 따라 성능의 변함이 없다. (그래프의 모양은 가로 1자)

 

O(n) : 입력데이터가 증가하면 처리시간도 증가한다. 언제나 데이터와 시간이 같은 비율로 증가한다. (그래프의모양은 정비례 직선)

 

O(n²) : 입력데이터를 돌리는 루프 안에서 또 입력데이터를 돌릴 때 (그래프의 모양은 초반은 시간 조금상승 후반은 수직상승)

 

O(n³) : 입력데이터n을 3중으로 돌릴 때 (그래프의 모양은 초반은 시간 조금상승 후반은 수직상승(더 급격히 상승))

 

O(nm) : 입력데이터1을 돌리는 루프 안에서 입력데이터2를 돌릴 때 (그래프의 모양은 초반은 시간 조금상승 후반은 수직상승)

 

O(2ⁿ) : 데이터의 증가에따라 시간이 왕왕증가많이됨

 

O(log n) : 대표적인 알고리즘은 이진검색이있음 / 한번 처리가 진행될 때 마다 검색해야 하는 데이터의 양이 절반씩 줄어들 때

 

상수는 버린다

왜냐면 실제 러닝타임을 표시하기보단 데이터나 사용자의 증가율을 예측하기 위한 표기법이기 ㄸㅐ문

 

 

 

엔지니어대한민국

[자료구조 알고리즘] 빅오표기법 완전정복 영상을 보며 작성하였습니다.