p.91 ~ p.126

반복문

알고리즘의 수행시간을 지배하는 것은 반복문

반복문의 수행 횟수는 입력의 크기에 대한 횟수로 표현

수행시간에 따른 알고리즘 분류

선형 시간 알고리즘

입력의 크기에 대비해 걸리는 시간을 그래프로 그리면 직선인 경우.

우리가 찾는 좋은 알고리즘.

선형 이하 시간 알고리즘

N을 계속 절반으로 나누는 일을 1이하가 될때까지 지속

lgN: 100,000 을 17번만 나누면 1에 도달 함

ex) 이진 탐색 알고리즘

• 정렬이 필요 A[ ]
• A[i-1] < x <= A[i]

다항 시간 알고리즘

반복문의 수행 횟수를 다항식으로 표현

대다수의 알고리즘에 해당

지수 시간 알고리즘

완전탐색 방식, 재귀호출을 통해 할지 말지 결정하는 알고리즘

ex) DFS

n 가지 경우, 모든 조합의 수 2ⁿ, 조합이 맞는지 여부 체크 m*n

∴ 재귀호출() 2ⁿ + isValid() m*n = mn2ⁿ

입력으로 주어지는 숫자의 갯수가 아닌 숫자의 값에 따라 지수시간이 될 수도 있음

시간 복잡도

시간복잡도가 높다

입력의 크기가 증가할 때 수행시간이 급격히 증가

시간복잡도가 낮다

입력의 크기가 증가해도 수행시간이 비슷

알고리즘 수행시간은 보통 최악의 시간을 측정

O 표기법 (Big-O Notation)

주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지 다 버림

정렬 알고리즘

선택 정렬은 무조건 O(N²)

삽입 정렬은 O(N) ~ O(N²) 까지 입력에 따라 다름

∴ 대부분의 경우 삽이 정렬이 더 빠름

∴ 삽입 정렬은 O(N²) 정렬 중 가장 빠른 알고리즘

수행 시간 어림짐작하기

1초 ≒ 1억

ex)

알고리즘 선택에 따른 수행 시간 비교

문제) 1차원 배열 연속된 부분 구간의 합이 최대인 구간

완전 탐색: O(N³)

반복문 2개 + 메모이제이션: O(N²)

분할 정복 알고리즘: O(NlgN)

동적 계획법: O(N)