이진탐색 : logN의 복잡도를 갖는다. 데이터양↑, 일의 양도 천천히 늘어남
가장 일반적인 경우 : 단순하게 N의 복잡도를 가지며 일의 양이 데이터와 정비례
퀵정렬 : NlogN의 복잡도를 가짐. N보다 효율이 낮지만, 로그 인자가 상당히 느리게 증가
-> 큰 N값에도 대단히 효과적으로 활용가능
N² : 일의 양이 너무 빨리 늘어나서 실행하기 힘들거나 활용 불가능
지수 복잡도
- 2ⁿ 비율로 증가 실생활에서 자주 등장하지만 효율이 낮다.
- 단 한개의 항목을 추가하면 수행해야 할 일이 '두 배'로 증가
- 지수 알고리즘은 logN알고리즘 (이진탐색)과 정 반대.
사실상 모든 가능한 경우를 하나씩 시도해봐야 하는 상황에서 발생
특히 함호 기법에 사용되여 특정 계산 과제를 수행하는 일이 지수 복잡도를 갖도록 하는것을 목적으로 한다.
실제로 발생하는 많은 문제나 그런 문제들의 근본이 되는 문제를 해결하기 위해 지수 알고리즘이 필요
이를 'NP문제' 라고 하는데 해결책을 빨리 찾을 수 없지만, 어떤 해결책을 알고 잇다면 그것이 맞는지를 빨리 입증이 가능
NP는 '비결정 다항' : 결정을 내려야 할 때 항상 옳게 추측하는 알고리즘이 있다면, NP문제가 그 알고리즘에 의해 다항 시간 내에 해결 될 수 있다는 뜻
가장 설명하기 쉬운 문제가 여행하는 외판원 문제
여행하는 외판원 문제: 자신이 사는 도시에서 출발하여 주어진 모든 도시를 반복 없이 방문하고 돌아오는 최소의 여행거리 문제
1971년 스티븐 쿡 : "정리 증명 절차의 복잡성" 논문에서 '우리가 그 문제 중 어느 한 문제를 해결하는 다항 시간 알고리즘 (N²등)을 찾을 수 있다면, 이 모든 문제의 대한 다항 시간 알고리즘을 찾아낼 수 있다는 것을 증명 →
1982년 튜링상 수상
다양한 복잡도를 다룰때 명심해야 되는 점
P=NP(난해 문제가 쉬운문제와 같은가)가 중요하긴하지나 현실적이라기보단 이론적인 주제
컴퓨터과학자가 말하는 복잡도 : 대부분 최악의 경우에 대한 것으로 보통은 여기까지 가지 않는다.
모든 문제를 난해하게 접근할 필요는 없다. 복잡도의 결과는 N이 큰 값일 때만 적용되는 점근적¹척도. 현실에서는 이러한 작동방식이 문제가 되지 않을 정도로 N이 작을 수도 있음.
실제 상황에서는 대부분 근사치만 구하는 것으로도 충분함.
단, 암호 시스템같은 응용분야는 특정 문제는 정말로 풀기 어려울 것이라 생각.
실효성이 없는 공격이더라도, 그 공격에 반격하는것은 대단해 중요.
¹대이터 개수가 무한대에 가까워지면 수행새간이 증가하는 비율을 가진 알고리즘의 복잡도를 분석하는 방식