자료구조) 시간복잡도

시간 복잡도

스텍

추가

O(1)

내가 추가할 곳이 정해져 있어서 

내가 뺼곳도 정해져 있어서 

linked list

검색, 추가 접근, 삭제

O(n)

끝까지 검색해야 해서

ps) 처음에 있을 때는 삽입과 삭제가 O(1)

 

위치를 알면 O(1)

위치를 모르면 O(n)

HashTable 삽입

O(1)

주소값이 유일하기  때문에, 각각의 주소값을 찾으면 되어서

충돌이  생길 경우

O(n)

 

 

두 알고리즘 A, B의 시간 복잡도가 각각 O(n), O(logn) 라면,

알고리즘 B가 알고리즘 A 보다 항상 빠르다.

=> 거짓

 

 

 

 

 

 

Big O Noration(빅-오 표기법) --- O(N)

가장 많이 쓰이는 표기법으로 알고리즘 실행시간의 상한을 나타낸 표기법(최악의 경우)

 

Ω(오메가)표기법 --  Ω(N)

오메가 표기법은 알고리즘 실행시간의 하한을 나타낸 표기법 (최상의 경우)

 

Θ(세타)표기법 --- Θ(N)

세타 표기법은 알고리즘 실행시간의 평균시간을 나타낸 표기법(평균의 경우)