알고리즘 시간 복잡도 분석

#1

알고리즘의 수행시간을 측정하는 기준은 바로 반복문이다.

선형시간알고리즘O(N)

• 다이어트 분포의 평균 구하기

선형이하시간알고리즘O(NlogN)

• 성형 전 사진 찾기(이진 탐색)

다항시간 알고리즘

• 시간복잡도가 O(N), O(N^2) … O(N^600)
• 다항 끼리의 시간차이도 엄청난다.

-소인수 분해

• 1보다 크고 소인수들만의 곱을 계산

파란색:선형이하시간 알고리즘

초록색:다항시간알고리즘

단 여기서 입력의 크기가 작으면 시간복잡도에 큰 의미를 주지는 않는다.

입력의 종류에 따른 수행 시간의 변화

입력의 크기 말고도 입력을 어떻게 받느냐도 중요함

삽입정렬을 예로 들자면 배열의 인수들이 가지런하게 정렬이 되어 있는 상태라면 O(1), 선형의 시간으로 본다면 O(N) , 최악은 O(N^2)

삽입 정렬을 흔히 사용되는 O(N^2) 정렬 중 가장 빠른 알고리즘이다.

분할 상환 분석

알고리즘의 시간 복잡도를 항상 반복문의 개수로 정하는 것은 아니다.

예를 들면 N명이서 N개의 라면을 먹는다고 한다면 누구는 많이 먹고, 누구는 적게 먹으면, 누구는 자신의 분량인 1개의 라면을 먹게 될 것이다. 하지만 평균적으로 보게되면 인당 하나씩 먹은 셈이다.

각 작업에 걸리는 시간은 다르지만 전체 갯수를 똑같이 나눈 것이다.

일반적으로는 오래걸려 실행이 안되는 것이 당연하지만 돌아가는 경우가 있다.

1초당 10^8(1억)이 넘으면 시간 초과이다.

1차원 배열을 생각을 해보자 [-7,4,-3,6,3,-8,3,4] 여기서 연속으로 최대합을 가지는 구간을 출력하는 문제를 생각해보자

정답은 [4,-3,6,-3]이다 이 문제는 여러가지의 알고리즘을 사용해서 풀 수가 있다.

1. 모든구간선회 O(N^2)개의 후보 구간을 검사, 각 구간의 합 O(N) 결국 O(N^3)이라는 결과를 갖게된다.
2. 분할정복 배열을 반으로 나누고 재귀,탐욕 사용해서 구한다. O(NlogN)
3. 동적 계획(dp) : 암튼 애는 O(N)이다.

각 테스트별 시간 제한을 1초 N의 크기를 1000 → 10,000 → 100,000 으로 증가한다고 생각해보자

N=1000 일때는 O(N^3)은 1억을 넘기는 하지만 반복문의 내부가 단순해서 통과할 확률이 있다.

N=10,000 N^3은 1억의 기준을 훨씬 넘기 때문에 통과하지 못한다. N^2는 간당간당하다

N=100,000 N^2는 100억이므로 안된다. NlogN은 2천으로 통과한다. N은 물론

알고리즘을 공부하는데 있어서 알고리즘을 증명하는 것을 하지 않는다면 알고리즘을 공부하는 것이 아니다. 알고리즘을 증명을 할 줄 알아야, 비로서 알고리즘을 사용하는 것이기 때문이다.

알고리즘 증명은 알고리즘을 유도 할 수 있는 가장 중요한 부분이다.

귀납법과 반복문 불변식

도미노를 예로 들어 수학적 귀납법에 대해 설명하겠다.

• 첫번째 도미노는 밀면 쓰러진다.
• 한 도미노가 넘어지면 다음 것도 쓰러진다.

수학적 귀납법은 이러한 반복적인 구조의 명제를 증명하는데 유용하게 쓰인다.

귀납법은 총 3단계로 이루어진다.

• 단계 나누기 : 증명하고 싶은 사실을 나눈다.
• 첫단계 증명 : 증명하고 싶은 내용의 성립
• 귀납증명 : 앞의 예가 성립하면 뒤에 내용도 성립한다.

또다른 예시는 “사다리 타기”

• 단계 나누기 : 텅빈 N개의 세로줄에서부터 시작해서 원하는 사다리가 될 때까지 가로줄을 그러 간다고 한다. 이때 가로줄을 하나 긋는 것을 한 단계라고 한다.
• 첫 단계 증명 : 텅빈 N개의 세로줄에서는 항상 맨 위 선택지와 맨 아래 선택지가 1:1 대응이 된다.
• 귀납 증명 : 가로줄을 그러서 두 개의 세로줄을 연결했다고 하자. 이때 두 세로줄의 결과는 서로 뒤바뀐다. 하지만 여전히 1:1대응을 이룬다.

반복문 불변식

귀납법으로 증명 할 때 “반복문 불변식”을 사용한다.

반복문 불변식이란 반복문의 내용이 실행 될때마다 중간 겨로가가 우리가 원하는 대로 진행되는지 알려주는 조건이다.

1. 반복문 진입시 식이 성립한다.
2. 반복문 내용이 식을 깨트리지 않는다.
3. 반복문 종료시에 성립하면 우리가 정답을 구했음이 보인다.

이진탐색을 예로 들자면

Array = [……]에서 left의 값을 lo right의 값을 hi로 두면

절대적인 불변식으로는 lo<hi , Array[lo] < x≤ Array[hi]

찾는 값보다 작으면 lo = mid, 크다면 hi = mid로 변경하면서 문제를 풀면 된다.

이러한 불변식은 코드를 오류없이 작성하는데 도움을 준다.

귀류법

구성적증명(Constructive proof)

답이 존재 한다고 앞의 나왔던 방법 처럼 논증 하는 것이 아니라, 실제 예를 제시하는 것 입니다.

하늘을 나는 교통수단이 있어 → 비행기를 보여준다, 비행기 설계도를 제시 한다.