Time Complexity 🧐

알고리즘이란?

• 어떠한 문제를 해결하기 위한 여러 동작들의 모임으로 유한성을 가진다.
• 한 문제를 여러가지의 알고리즘으로 풀 수 있기 때문에 time complexity를 설명하는데 사용된다.
• 시간복잡도란 input에 대하여 알고리즘이 문제를 해결하는데 얼마나 시간이 걸리는지를 표현하며 Big-0 표기를 이용하여 정의할 수 있다.

Big-O Notations

Constant Time(상수 시간)

• O(1) : 값을 검색할 때 키를 알거나 배열의 인덱스 값을 알고 있으면 입력되는 데이터 양과 상관 없이 일정하게 실행된다.

Logarithmic Time(로그 시간)

• O(log n) : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.

  👉🏻 example
  배열에서 값을 검색할 때 어디에서 시작할지 알고 있으면 검색시간이 두배로 줄어든다.

Linear Time(Binary Search)

• O(n) : 입력 데이터 양에 따라 수행 시간이 비례한다.

Linearithmic Time(선형 탐색, for 문)

• O(n log n) : 입력 데이터 양이 n배 많아질수록 수행시간은 n배보다 더 많아진다.

Quadratic Time(지수 시간)

• O(n^2) : 입력 데이터 양에 따른 수행시간은 제곱에 비례한다.

  👉🏻 문제를 풀기 위해 모든 조합을 사용할 경우

---

Ref)
https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/
https://www.holaxprogramming.com/2017/12/29/algorithms-learning-strategy/
https://towardsdatascience.com/understanding-time-complexity-with-python-examples-2bda6e8158a7
https://stackabuse.com/big-o-notation-and-algorithm-analysis-with-python-examples/