우아한Tech [10분 테코톡] 시간 복잡도

시간복잡도    - 알고리즘과 밀접한 연관이 있음 // 알고리즘 ) 문제를 해결하기 위한 방법

                      - 문제를 해결하는데 걸리는 시간과 입력의 함수관계

 

-> 뒤에 있는 연산이 핵심/복잡도

복잡도를 나타내는 그래프

log n 이 가장 현실세계에서 이상적인 알고리즘이라고 평가됨.

지수 형태로 올라가는 알고리즘은 사실상 풀 수 없는 알고리즘 이라고 함.

 

그렇다면 어떤게 현실적이고 어떤게 비현실 적인가?

 

현실적 알고리즘

- Polynomial complexity (P 문제) , sorting. dp....

- 상식선에서 풀 수 있는 문제

- 정렬 등

 

비현실적인 알고리즘

-Nondeterministic Polynomial complexity (NP 문제)

-복잡도가 팩토리얼이나 지수형태로 올라가면 비현실적인 알고리즘

-해밀턴 경로 문제

 

NP 문제 소인수분해문제

3*7=21

21=3*7  -> 컴퓨터는 오랜 시간이 걸림, 큰 수자면 더 오래 걸림

컴퓨터에서 소인수 분해가 어렵다는 점(비현실적 시간 복잡도)을 이용한 공인인증서

P = NP 되면, 아무것도 안해도 알고리즘도 금방 풀어버리게 되서, 이 세상은 사이버 공간이라는 말도 나올것임...

 

오늘의 키워드: 37의 법칙

                          P-NP

 

자료: https://www.youtube.com/watch?v=IEH3YA2Nn4Q