시간복잡도

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

 

핵심이 되는 연산이 무엇일까? 

n**2 + 2n -> O(n**2)

 

{ for i<N:

  for j<M:

    for ( k<1000) 

} -> 시간 복잡도 => O(N**2) 마지막 for은 상수기 때문에 무시가능 

 

{ for i <n; i =i*2 } => O(logn) i가 2의 배수만큼 뛰기 때문에 

 

현실적 알고리즘 (Polynmial complexity) p문제

sorting, dp 

 

비현실적 알고리즘 (Nondeterministic Polynmial complexity) np문제

헤밀턴 경로 문제, 팩토리얼 문제, 소인수분해 -> 공개키, 비밀키 보안 알고리즘 

 

www.youtube.com/watch?v=IEH3YA2Nn4Q&list=PLgXGHBqgT2TvpJ_p9L_yZKPifgdBOzdVH&index=86