[Python] 시간복잡도

알고리즘을 풀다가, 같은 연산인데도 불구하고 사람들마다 걸리는 시간이 다르다는걸 알게되었다.

그래서 관심을 갖고 조사를 해보았다.

시간복잡도란?

한마디로 시간이 얼마나 걸리느냐

시간복잡도는 주로 빅-오(Big-O)표기법을 사용하여 나타낸다.

복잡한 정도

• O(1) < O(log(n)) < O(nlosg(n)) < O(n^2)

n의 차수가 높아질수록 시간 복잡도가 올라가고 그만큼 시간이 오래 걸린다고 생각하면 될꺼 같다.

자료형에 따른 시간 복잡도

List 자료형

아직 많은 자료형을 사용해보지 못했기 때문에, 나는 엄청나게 와닿지는 못했으나,
이 표를 보고 알 수 있는 것은

1. Sort 연산자는 퀵정렬 형식으로 효율적.
2. pop이나 delet연산의 경우, 전체 리스트의 요소를 움직여 줘야 하는 등의 이유로 결국 O(N)의 복잡도를 가지는 것을 확인.

Set 자료형

Dictionary 자료형

list 자료형에 비해 Set자료형이나, Dictionary자료형은 element를 추가하거나 삭제하는데 복잡도가 O(1)으로, 부담이 더 적은 편임을 알 수 있었다.

참고 : ttps://chancoding.tistory.com/43