♻️시간 복잡도

어떤 알고리즘으로 풀어야 할까 ?

알고리즘 선택의 기준 ⇒ 시간복잡도

[정의]

주어진 문제를 해결하기 위한 연산 횟수

python → 2000만 번 ~ 1억 번의 연산을 1초의 수행 시간으로 예측

연산 횟수는 1초에 2000만 번을 기준으로 생각,,

[유형]

• 빅-오메가 : 최선일 때의 연산 횟수
• 빅-세타 : 보통일 때의 연산 횟수
• 빅-오 : 최악일 때의 연산 횟수

import random
findNumber = random.randrange(1, 101) # 1~100 사이 랜덤값 생성

for i in range(1, 101):
    if i == findNumber:
        print(i)
        break

• 빅-오메가 : 1번
  • 최선일 때 → 첫 번째 시도에 찾는 경우
• 빅-세타 : N/2번 (N은 데이터 개수)
  • 보통일 때 → 절반쯤 찾는 경우
• 빅-오 : N번
  • 최악일 때 → 100번째(마지막) 찾는 경우

코딩테스트에서는 빅-오 표기법 사용 → O(n)

⇒ 항상 최악의 경우 생각하기

코딩 문제에서 데이터 범위 확인(제일 큰 수 확인) !!

[연산 횟수 계산 방법]

• 연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출

ex)

데이터 범위 : 0 ~ 100,0000

시간 제한 : 2초

⇒ 조건을 만족하려면 4000만 번 이하의 연산 횟수로 해결 필요

[사용가능한 2개의 알고리즘]

• 버블 정렬
  • O(n^2) → (100만)^2 > 4000만 번 👉🏼 부적합
• 병합 정렬
  • O(nlogn) → (100만)log(100만) < 4000만 번 👉🏼 적합

[시간 복잡도 도출 기준]

1. 상수는 시간 복잡도 계산에서 제회
2. 가장 많이 중첩된 반복문의 수행 횟수

N = 100000
cnt = 1

for i in range(N):
    print("연산 횟수" + str(cnt))
    cnt += 1

연산 횟수 = N

N = 100000
cnt = 1

for i in range(N):
    print("연산 횟수" + str(cnt))
    cnt += 1
    
for i in range(N):
    print("연산 횟수" + str(cnt))
    cnt += 1
    
for i in range(N):
    print("연산 횟수" + str(cnt))
    cnt += 1

연산 횟수 = 3N

⇒ 3배 차이

코딩 테스트에서는 상수를 무시하므로 시간복잡도는 O(N)으로 동일함

N = 100000
cnt = 1

for i in range(N):
    for j in range(N):
        print("연산 횟수" + str(cnt))
        cnt += 1

연산 횟수 = N^2

중첩이 있는 부분 O(N^2) → 시간 가장 많이 걸리기 때문