[알고리즘/C++]시간 복잡도와 시간 제한

연산 횟수

• 연산 횟수는 1초에 1억번입니다.
• 시간 복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준으로 합니다.
• 연산 횟수 계산 방법
  • 연산 횟수 = 알고리즘 시간 복잡도 N값에 데이터의 최대 크기를 대입해 도출

예시

시간 제한이 2초이고, N (1 ≤ N ≤ 1,000,000)개의 수가 주어졌을 때 오름차순으로 정렬하는 문제

• 버블 정렬은 시간 복잡도가 O(n^2)입니다.
  • 버블 정렬의 연산 횟수 = (1,000,000) ^ 2 = (1,000,000,000,000) > 200,000,000 ⇒ 시간초과 발생
    
• 병합 정렬의 시간 복잡도는 O(nlogn)입니다.
  • 병합 정렬의 연산 횟수 = 1,000,000 log2(1,000,000) = 약 20,000,000(2천만) < 200,000,000 (2억) ⇒ 적합한 알고리즘
    

외우면 좋을 것들

• 저는 너무 큰 숫자를 보면 단위가 한 눈에 들어오지 않아서 외우면 좋을 것 같다 싶었습니다.
• 1,000,000 : 100만 (10^6)
• 100,000,000: 1억 (10^8)
• 2,100,000,000: 21억 (10^9 * 2.1) => int 자료형의 범위
• 1,000,000,000,000: 1조 (10^12)
• 1,000,000 log2(1,000,000) = 약 2천만
• 10,000 * log2(10,000) = 약 12만