시간 복잡도 분석과 알고리즘 정당성 증명

시간 복잡도

가장 널리 사용되는 알고리즘 수행 시간 기준. 알고리즘이 실행되는 동안 수행하는 기본적 연산의 수를 입력의 크기에 대한 함수로 표현한 것

알고리즘의 수행 시간은 반복문이 지배!

• C++에서 vector, string등의 크기가 큰 구조체를 함수 인자로 넘길 때는 참조형으로 넘기자 (훨씬 빠르게 동작함)
  
  
• 주먹구구 법칙
  입력의 크기를 시간 복잡도에 대입해 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한 초과할 수 가능성 있다
  
  
• P 문제 : 다항 시간 알고리즘이 존재하는 문제들의 집합
  
  
• NP 문제 : 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제

~ 모든 P 문제는 NP 문제에 포함

ex) big-O
O(N+P), P < N/2 -> O(N)
O(2N) -> O(N)
O(N + logN) -> O(N)
O(N + M) -> O(N + M)

알고리즘의 정당성 증명

1. 귀납법
   단계 나누기 -> 첫 단계 증명 -> 귀납 증명

       // 불변식 성립
     while (어떤 조건) {
         //반복문 내용 시작
         ..  

반복문 내용이 불변식을 깨뜨리지 않고, 반복문 종료시에 불변식 성립하면 정답 구현한 것

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