2022.07.15

p101~150 

지수 시간 알고리즘

 다항 시간 알고리즘보다 시간 훨씬 더 많이 걸림. 

모든 답을 한 번씩 다 확인하는 경우 전체 걸리는 시간은 만들 수 있는 답의 수에 비례함. 지수 함수는 알고리즘의 전체 수행 시간에 엄청난 영향을 미침. 아직 지수 시간보다 빠른 알고리즘을 찾아내지 못한 문제 아주 많음. 다항 시간과 지수 시간 사이의 경계는 전산학에서 효율적으로 해결할 수 잇는 문제와 없는 문제를 가르는 경계. 따라서 다항 시간 알고리즘이 있는 문제는 계산적으로 쉬운 문제, 없는 문제는 어려운 문제임. 

 

소인수 부해의 수행 시간 

소인수 분해 문제에서는 입력으로 주어지는 숫자가 알고리즘의 동작에 직접적인 영향을 미치므로 숫자가 특정 범위 안에 있다고 가정할 수 없음. 비트의 수가 하나 증가할 때마다 표현할 수 잇는 수의 범위와 알고리즘의 최대 수행 시간은 두 배로 늘어남. 즉 입력의 크기를 입력이 차지하는 비트 수로 정의하면 입력의 크기에 대해 지수 시간이 걸린다고 말할 수 있음. 

 

시간 복잡도 

알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것. 

시간 복잡도 높다 = 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다. (단 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니다)

입력의 형태가 어떤 형태로 구성되어 잇는지도 수행 시간에 영향을 미침. 입력의 종류에 따라 수행 시간이 달라지는 경우를 고려하기 위해 우리는 최선, 최악의 경우 그리고 평균적인 경우에 대한 수행 시간을 따로 계산할 필요가 잇음. 대개 최악의 수행 시간 혹은 수행 시간의 기대치를 많이 사용함. 

 

점근적 시간 표기: O 표기 

주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법. 이 표기법을 쓸 때 알고리즘의 시간 복잡도는 반복문에 의해 결정되므로 반복문들이 몇 번이나 실행되었는지만을 보면 됨. 

 

O표기법의 의미

대략적으로 함수의 상한을 나타낸다는데 의미가 있음. 특별히 최악의 수행 시간과 관련이 있는 것은 아님. 

 

시간 복잡도의 분할 상환 분석

N개의 작은 작업들을 순서대로 하는데 각 작업에 걸리는 시간은 모두 다르지만 전체 작업에 걸리는 시간이 일정한 경우 이런 방법을 적용할 수 있다. 이때 각 작업에 걸리는 평균 시간은 전체 시간을 작업의 개수로 나눈 것과 같다고 할 수 있다. 

 

수행 시간 어림짐작하기 

주먹구구 법칙

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해 1초당 반복문 수행 횟수가 1억을 넘어가면 시간 제한을 초과할 가능성이 있다. 

시간 복잡도 외에도 다른 요소들을 참조해야 하는 경우들 

1. 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우

2. 반복문의 내부가 복잡한 경우

3. 메모리 사용 패턴이 복잡한 경우

4. 언어와 컴파일러의 차이

5. 구형 컴퓨터를 사용하는 경우 

 

계산 복잡도 클래스: P, NP, NP-완비

 어려운 문제의 기준이 된느 것 = SAT 문제 

N개의 불린 값 변수로 구성된 논리식을 참으로 만드는 변수 값들의 조합을 찾는 문제이다. SAT 문제는 모든 NP 문제 이상으로 어렵다. 

NP 문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제. 모든 P문제들은 모두 NP 문제에도 포함된다. SAT 가 모든 NP 문제 이상으로 어렵다는 말은 SAT 를 다항 시간에 풀 수 있으면 NP 문제들을 전부 다항 시간에 풀 수 있다는 얘기. 이런 속성을 갖는 문제들의 집합을 NP-난해 문제라 함. NP-난해 문제이면서 NP인 문제들 = NP-완비 문제 라고 함. 

 

수학적 귀납법과 반복문 불변식 

귀납법 증명 

1. 단계 나누기

2. 첫 단계 증명

3. 귀납 증명 

 

반복문 불변식 

반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건. 

불변식을 이용하면 반복문의 정당성을 다음과 같이 증명할 수 있습니다. 

1. 반복문 진입 시에 불변식이 성립함을 보인다.

2. 반복문 내용이 불변식을 깨뜨리지 않음을 보인다. 다르게 말하면 반복문 내용이 시작할 때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다. 

3. 반복문 종료 시에 불변식이 성립하면 항상 우리가 정답을 구했음을 보인다. 

 

단정문을 이용해 반복문 불변식을 강제하면 해당 불변식이 깨졌을 때 프로그램이 강제 종료되므로 불변식의 유지에 문제가 있다는 사실을 쉽게 알 수 있음. 

 

귀류법

우리가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법 

 

기타 기술들 

비둘기집 원리

10마리의 비둘기가 9개의 비둘기집에 모두 들어갔다면 2마리 이상이 들어간 비둘기집이 반드시 하나는 있게 마련이다.

동전 뒤집기

비둘기집 원리 이용 

순환 소수 찾기

비둘기집 원리 이용 (결과가 중복되는 경우가 반드시 있을 것. 같은 결과가 첫번째로 등장햇을 때부터 두번째 등장할 때까지 무한히 순환되는 소수임.)

구성적 증명

우리가 원하는 어떤 답이 존재한다는 사실을 증명하기 위해 사용됨. 

안정적 결혼 문제

 종료 증명

 모든 사람들이 짝을 찾는지 증명 -> 귀류법 증명

 짝들의 안정성 -> 귀류법으로 증명 

 

무식하게 푼다 = 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법 = 완전탐색

재귀 호출과 완전 탐색 

재귀 함수 = 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고 나머지를 자기 자신을 호출해 실행하는 함수. 모든 재귀 함수는 더이상 쪼개지지 않는 최소한의 작업에 도달햇을 때 답을 곧장 반환하는 조건문을 포함해야 함. 이때 쪼개지지 앟는 가장 작은 작업들을 재귀 호출의 기저 사례라고 함.