Time Complexity/ Space Complexity

✅ Time Complexity

time taken by an algorithm
to run as a function of the length of the input
시간복잡도: 입력 크기 n에 대해 걸린 시간을 함수T(n)로 표현

• 상수는 1로 취급
• 가장 영향력이 큰 값(dominant)만을 나타낸다.

• Example: T(n) = 2n^2 + n + 1일 경우, O(n^2)

• Big-O: 최악의 경우
• Big-Ω: 최선의 경우
• Big-θ: 최악, 최선의 평균

복잡도 순서: O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!)

✔️ O(1)

• 상수
• 실행 시간은 입력 크기와 관계없이 일정
• search in hash table

✔️ O(N)

• 선형
• 실행시간과 입력 크기가 비례
• 입력 크기 ⬆️ 실행 시간 ⬆️
• compare all elements in list to a certain value

✔️ O(N^2)

• 실행 시간은 입력 크기의 제곱 함수
• for in for loop
• check two different lists for matching value

✔️ O(2^N)

• 실행 시간은 입력 크기에 따라 기하급수적으로 증가
• 👎🏻 매우 비효율적
• three-coloring problem

✔️ O(log N)

• 입력 크기가 크게 증가해도 실행 시간은 선형적으로 증가
• [입력 크기 1000개, 실행 시간 1초], [입력 크기 100000개, 실행 시간 2초], [입력 크기 10000000개, 실행 시간 3초]…
• binary search

🆚 Time complexity of sorting algorithms

• Big-O 기준으로

• quick sort is the fastest

✅ Space Complexity