[소프트웨어] 22번

지수 복잡도(expnential) 복잡도.

• 2^N의 비율로 일의 양이 빠르게 증가.
• 암호 기법에 사용되는 알고리즘은 특정 계산 과제를 수행하는 일이 지수 복잡도를 갖도록 하는데 기반을 둠. 
• 하나하나 푸는데 계산상으로 불가능할 정도로의 큰 N을 기반으로 복호화를 방지

 

지수복잡도의 대표적인 예

하노이의 탑

1. 한 번의 하나의 원판만 이동할 수 있다.
2. 맨 위의 있는 원판만 이동이 가능하다.
3. 크기가 작은 원판위에 큰 원판이 쌓일 수 없다.
4. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다
   
   

출처: https://lipcoder.tistory.com/72

재귀를 이용한 피보나치 수열

def fibo(n):
    if n==1 : return 1
    if n==2 : return 1

    return fibo(n-1)+fibo(n-2)

 

 

P, NP문제

답이 YES 아니면 NO로 반환되는 문제를 결정 문제라고 한다. 예를 들어 'a는 b의 배수인가?'와 같은 질문은 결정 문제다. P와 NP는 모두 결정 문제의 분류에 해당한다.

P 문제는 결정 문제들 중 쉽게 풀리는 것을 모아 놓은 집합이다. 어떤 결정 문제가 주어졌을 때, 다항식(Polynomial) 시간 이내에 그 문제의 답을 계산해낼 수 있는 알고리즘이 존재한다면, 그 문제는 P 문제에 해당된다. 이 정의는 결정적 알고리즘(deterministic algorithm), 즉 계산의 각 단계에서 단 한 가지의 가능성만을 고려할 수 있는 알고리즘이 다항 시간이 걸리는 문제가 P 문제라는 뜻이다. 

NP란, Non-deterministic Polynomial의 약자로 형식적으로는 문제를 푸는 각 단계에서 여러 가지의 가능성을 동시에 고려할 수 있는 비결정적 알고리즘(non-deterministic algorithm)으로, 다항시간 내에 문제를 해결할 수 있는 문제라고 정의한다. 즉, NP문제는 해결방법을 찾기 어렵지만 답을 제시하면 맞는지 틀린지 판별하기는 쉬운 문제라고 할 수 있으며 경우의 수를 전부 확인하면서 문제를 푸는 방법으로 해결하는 문제들이 많다,