O(n log n)
입력 n개 각각에 대해 log n번쯤 일을 하는 정도의 시간이다. log n은 n을 반으로 몇 번 나누면 1이 되는지를 센 수다 — n이 1,024면 10번이라 log n은 10이다. 그래서 n이 1,024일 때 O(n²)은 약 100만 번, O(n log n)은 약 1만 번이다. 배열을 반씩 나눠 가며 정렬하는 퀵 · 병합 · 힙 정렬이 이 속도를 낸다.
자신만의 철학을 만들어가는 중입니다.
최상단으로 이동했습니다!
자신만의 철학을 만들어가는 중입니다.