시간복잡도

• 알고리즘이 어떤 문제를 해결하는데 걸리는 시간
  빅-오 표기법
  
  n은 데이터의 크기를 나타낸다

• O(log₂n)
  입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 됩니다. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당됩니다.

• O(n)
  입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됩니다. '1차원 for문'이 있습니다.

• O(n log₂ n) (Linear-Logarithmic)
  데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 정렬 알고리즘 중 '병합 정렬, 퀵 정렬'이 대표적입니다.

• O(n²)
  데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다. 이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직합니다. '이중 for문'