계산복잡도 vs 시간복잡도

 

• 계산복잡도는:
  → “문제 자체가 풀리는 데 필요한 최소 시간”
  → 이건 문제 전체의 하한선
• 시간복잡도에서의 최선은:
  → “어떤 알고리즘이 특별히 좋은 경우에 걸리는 시간”
  → 이건 특정 알고리즘의 최선의 경우

즉,

• 계산복잡도는 “문제 입장”에서의 최선
• 시간복잡도는 “알고리즘 입장”에서의 성능 (평균, 최악, 최선)

 

✈️ 비행기를 타고 서울 → 부산 간다고 하자

• 계산복잡도:
  ✨ "서울에서 부산까지 갈 수 있는 가장 빠른 수단으로 걸리는 최소 시간"
  → 비행기 타면 1시간. 이게 계산복잡도.
• 시간복잡도의 최선:
  🚗 어떤 사람이 차를 타고 갔는데
  • 평소엔 5시간 걸리지만
  • 오늘은 도로가 뻥 뚫려서 3시간 걸림
    → 이게 특정 알고리즘(=차) 의 최선 시간

🚨 즉, 비행기(=최고 알고리즘)가 있을 수 있는데,
자동차(=다른 알고리즘) 가 최선일 땐 더 빠를 수도 있는 것처럼 보일 수도 있다.
하지만 문제의 본질은 비행기보다 빨리 갈 수는 없다는 것 → 이게 계산복잡도

 

 

예외 (특수 정렬)

비교하지 않고 정렬할 수도 있음:

• 숫자가 0부터 100 사이처럼 범위가 작으면?
• 또는 자릿수를 기준으로 나누면?

이런 경우는 비교 없이, 더 빠르게 정렬 가능

이들은 O(n), 즉 선형 시간에 정렬 가능 (비교 정렬보다 빠름)