[Python] Time Complexity of List (Big-O)

백준이나 프로그래머스에서 코딩 테스트를 연습하다 보면 시간 초과가 뜨는 경우가 종종 있었다.
이 때, 가장 중요한 개념 중 하나가 시간 복잡도! 이를 정확히 알고 있으면 코딩 테스트 시간을 단축 시킬 수 있다. 😤

✔ 시간 복잡도

정의 : 문제를 해결하는데 걸리는 시간과 입력의 함수 관계 
알고리즘의 시간 복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다.
알고리즘의 시간복잡도는 주로 빅오 (Big-O) 표기법을 사용하여 나타낸다.

---

✔ 표기법

 1.  $O(1)$ : 상수 시간

  - random access 가능

 2. $O(logN)$ : 로그 시간

  - 입력 크기 ($N$)가 커질 때, 연산 횟수가 $logN$에 비례해서 증가하면 시간 복잡도는 $O(logN)$ 이다
  - 로그 시간이 걸리도록 코드를 짜는 것이 가장 좋다...🌝

3. $O(N)$ : 선형 시간

  - 연산횟수가 선형적으로 증가하는 형태이다

4. $O(N^2)$ : 2차 시간

  - 이중 for문의 경우, 이에 해당한다. 

복잡한 정도!

---

✔ 자료형 Big-O 표기법

📁 List Big-O

📁 Dictionary Big-O