Big-O는 알고리즘의 효율성을 나타내는 지표 혹은 언어이다. Big-O는 알고리즘 실행속도의 상한을 나타내는 지표로, 하한을 나타는 Big-Omega, 상한과 하한 둘 다를 나타내는 Big-Theta가 있으나 Big-O를 가장 많이 사용함.

• 알고리즘 수행 시간을 최선의 경우, 평균적인 경우, 최악의 경우로 나눌 수 있다.
• 퀵소트를 예시로 들면, 배열의 모든 원소가 같다면 단순히 배열을 한차례 순회하고 정렬이 끝날 것이다. 이경우 수행시간은 O(N)이 된다. 최악의 경우 피벗이 되는 수가 배열에 가장 큰 원소가 되는 경우로, 수행시간이 O(N^2)이 된다. 평균적으로는 O(NlogN)이 될 것이다.
• 최선의 경우에 시간복잡도는 별로 쓸만한 개념이 아니기 때문에, 유용하다고 말하기는 힘들다. 어떤 특수한 경우를 찾아 동작시간이 무조건 O(1)이 되도록 하는것은 어려운 일이 아니다.
• 대부분의 알고리즘은 최악의 경우와 평균적인 경우가 같다.
• Big-O는 단순히 증가하는 비율을 나타내는 개념이다. O(N)이 언제나 O(2N)보다 낫지 않을 수 있다. 따라서 상수항은 무시한다.
• 지배적이지 않은 항은 무시하라.
  • O(N^2 + N)은 O(N^2)이 된다.
  • O(N + logN)은 O(N)이 된다.
  • O(5*2^N + 1000N^100)은 O(2^N)이 된다.
• O(logx) < O(x) < O(xlogx) < O(x^2) < O(2^x) < O(x!)

• 여러 부분으로 이루어진 알고리즘
  • A를 수행 한후 B를 수행하는 경우 O(A + B)
  • A루프 안에 B루프가 있는 경우 O(A*B)

logN 수행시간

• 이진 탐색을 생각 해 보면 처음 N개의 원소가 들어있는 배열에서 어떤 수를 찾을 때, 단계를 거칠 때 마다 탐색 할 원소의 개수가 N → N/2 → N/4 로 줄어든다.
• 즉, 2^k = N 을 만족하는 k는 무엇인가? log2N = k
• 어떤 문제에서 원소의 개수가 절반씩 줄어든다면 그 문제의 수행 시간은 O(logN)이 될 가능성이 크다.