시간 복잡도

빅오 표기법 (Big O Motation)

Time Complexity를 표기하는 방법
여러 알고리즘의 성능을 비교/판단해 볼 수 있는 지표
어떤 동작을 수행할 때 최악의 경우 걸리는 시간을 표기하는 방법

• "아무리 최악이더라도 이 정도는 넘지 않겠구나"

Case Study

O(1),O(logN), O(N), O(NlogN), O(N²), O(N³), ..., O(2ⁿ), O(N!)

• 괄호 안의 동작을 수행할 때, 최악의 경우 걸리는 시간을 표기하는 방법
• Big O notation은 n이 증가함에 따라 처리 시간의 증가하는 형태를 나타낸다
  • 따라서 O(kn)에서 k가 상수일 경우, 상수 k를 무시하여 O(n)으로 표기하게 된다.
• 오른쪽으로 갈수록, 기울기가 가파를수록 최악의 경우로 본다.
  • O(1) : 최선의 경우(Best Case)
  • O(N!): 최악의 경우(Worst Case)
  • O(NlogN): 여기까지는 괜찮다고 여겨진다
  • O(N²): 여기서부터 좋지 않다고 여겨진다
    

출처

• Time complexity and Big O Notation - heyday_7.log
• (Algorithm) 시간의 복잡도 - ZeroCho Blog