Do it 알고리즘 코딩테스트 하루코딩 1장 시간복잡도 이론

#1 시간 복잡도 java

알고리즘 선택의 기준이 되는 시간 복잡도 (by소거법)

 

시간복잡도 == 수행시간 == 연산횟수

자바 1초 == 1억번

 

시간복잡도 유형

1. 빅오메가: 최선(best case)일 때 연산 횟수, 즉 1

2. 빅세타: 보통(average case)일 때 연산 횟수, 즉 N/2

3. 빅오: 최악(worst case)일 때 연산 횟수, 즉 N

 

코딩테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까?

빅오 표기법

다양한 테스트 케이스를 수행해 모두 통과해야 하므로

 

데이터의 크기 증가에 따른 수행시간 증가율

O(1)

O(logn)

O(n)

O(nlogn)

O(n^2)

O(n^3)

O(2^n)

O(n!)

 

연산횟수 계산방법

알고리즘의 시간복잡도에 데이터의 최대 크기 N 대입

ex) O(n^2) 의 시간복잡도인 알고리즘으로 데이터의 최대크기가 100인 프로그램의 연산횟수는 O(100^2)

 

시간복잡도 도출 원리

1. 상수 제외

2. 가장 많이 중첩된 반복문 등 즉, 상항(가장 빠르게 증가하는 항)만을 고려

ex)

3N == N

N^2 + N + 3 == N^2

 

시간 초과가 발생할 때

1. 알맞은 알고리즘을 선택하였는지?

2. 비효율적인 로직 개선

 

#2 시간복잡도 python

파이썬 1초 == 2천만번