T(n)

T(n): 크기가 N인 입력에 대해 정렬이 수행하는 원소 비교 횟수

알고리즘의 실제 실행 시간,
입력에 따라 몇 번의 연산이 이루어지는지 정확하게 계산한 값

O(n): 알고리즘의 성능을 입력 크기 n에 대한 상한으로 설명

만약 어떤 알고리즘이 T(n) = 3n + 2와 같은 실행 시간을 가진다면, O(n)은 상수 항목을 무시하여 O(n) = n이 됩니다.

[ 퀵정렬 ] 

• 최선의 경우: 피벗이 매번 입력을 1/2씩 분할하는 경우
  • T(n) = 2T(n) + cN
  • T(1) = c'으로 합병정렬의 최선의 수행시간과 동일
• 평균의 경우: T(n) = O(NlogN)
• 최악의 경우: 피벗이 매번 가장 작을 경우 또는 가장 클 경우
  • T(n) = T(n-1) + n-1, T(1) = 0
  • T(n) = n * (n - 1) / 2 = O(n^2)