Time Complexity

• 시간 복잡도는 문제를 해결하는데 걸리는 시간을 의미합니다.
• 보통 시간 복잡도는 최악의 경우를 가정하여 표현합니다 → Big(O)

Better → Worse
O(1) < O(log n) < O(n) < O(n^2) < O(2^n)

• O(1) constant time : 언제나 일정한 시간이 걸리며, 문제를 해결하는데 단 한 번으로 끝납니다.

• O(n) linear time : 문제를 해결하는데 데이터 크기와 비례합니다.

• O(log n) log time : 데이터의 양이 많더라도 시간은 조금씩 증가합니다.

  • Binary Search Tree : Search, Insert, Delete

• O(n^2) quadratic time : 데이터 크에 따라 걸리는 시간이 제곱에 비례합니다.

  • Multiple Loops