알고리즘 문제해결 전략 1권 정리(CH-4 알고리즘의 시간복잡도 분석)

시간 복잡도

앞 절들에서 우리는 깊이 중첩된 반복문의 수행 횟수를 계산했습니다.
가장 깊이 중첩된 반복문의 내부에 있는 기본적 연산들은 더 쪼갤 수 없기 때문에,
이것이 시간 복잡도의 대략적인 기준이 됩니다.
-4.5 시간복잡도 106p-

시간 복잡도가 높다?

• 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다.
• 단, 시간 복잡도가 낮다고 해서 언제나 빠르게 동작하는 것은 아니다!

입력의 종류에 따른 수행 시간의 변화

• 입력의 크기가 수행 시간을 결정하는 유일한 척도는 아니다.
• 입력이 어떤 형태로 구성되어 있는지도 수행 시간에 영향을 미친다.
  • 이와 같이 입력의 종류에 따라 수행 시간이 달라지는 경우를 고려하기 위해
    최선/최악 그리고 평균적인 경우에 대한 수행 시간을 각각 따로 계산한다.
  • 위의 3가지 기준 중 사람들이 대개 사용하는 것은 최악의 수행 시간 혹은 수행 시간의 기대치이다.

점근적 시간 표기: O 표기

• 시간 복잡도는 알고리즘의 수행 시간을 표기하는 방법이지만, 계산하기 너무 힘들다는 문제가 존재
• 따라서, 이것을 간단하게 표현한 대문자 O 표기법(Big-O Notation)이라는 것을 사용해 알고리즘의 수행시간을 표기한다.

  O 표기법은 간단하게 말해 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법이다.

  ex.) f(N) = 4N^2 + 124N + 123 -> O(N^2)

수행 시간 어림짐작하기

주먹구구 법칙

위와 같은 O표기법을 통해 얻은 데이터로 수행 시간을 어림잡아보자

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반목문의 수행 획수가 1억을 넘어가면 시간 제한을 초과할 가능성이 있다.

• 위의 기준을 이용해 입력의 최대 크기 N이 10000이면 O(N^3)은 1억을 훨씬 초과하고, O(NlogN)은 1억에 못미친다.
• 이때, O(N^2)같이 1억을 초과하진 않지만 애매모호 한애들은 직접 실행해보지 않고서는 모른다.
• 왜냐하면, 시간 복잡도와 입력의 크기 외의 요소들이 프로그램의 수행 속도를 열 배 정보는 쉽게 바꿔 놓을 수 있기 때문이다.
• 이와 같이 이법칙을 적용할 때는 충분한 여유를 두는 것이 좋다.(ex. 예측한 수행횟수 기준 10%이하 or 기준을 10배증가)

주먹구구 법칙은 주먹구구일 뿐

주먹구구 법칙은 수많은 가정 위에 지어진 사상누각이기 때문에, 절대 맹신해서는 안 된다.
주먹구구 법칙에서 알려주지 않은 각종 수행시간 관련 요소들은 아래와 같다.

• 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우
  • O 표기법으로는 최고차항 이외의 항들을 모두 지워버리기 때문에 시간 복잡도 식에 입력의 최대 크기를 대입한 결과는 어디까지나 적당한 예측 값일 뿐이다.
    
    
• 반복문의 내부가 복잡한 경우
  • 반복문 내부가 길거나 시간이 많이 걸리는 연산(실수 연산, 파일 입출력 등)이 있으면 가정보다 오래걸린다.
    
    
• 메모리 사용 패턴이 복잡한 경우
  • CPU의 캐시 사용에 최적화 되게 짜지 않으면 차이가 좀 많이 난다. (Special loccality, Temporal locality)
    
    
• 언어와 컴파일러의 차이
• 구형 컴퓨터를 사용한 경우(오래된 옛날 CPU는 당연히 느리다..)

P, NP

• P: 다항 시간 알고리즘이 존재하는 문제들의 집합을 P문제라 한다.
• NP: 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 NP문제라 한다.
• SAT: N개의 불린 값 변수로 구성된 논리식을 참으로 만드는 변수 값들의 조합을 찾는 문제, 보통 어려운 문제의 기준이됨
• NP-Hard: 적어도 NP문제 보다는 어려우며, “모든” NP 문제를 다항 시간 내에 어떤 문제 A로 환원(reduction)할 수 있다면, 그 A 문제를 NP-난해(NP-hard) 문제라고 한다.
• NP-Complete: NP 난해 문제에도 포함되며, NP 문제에도 포함된다면 이를 NP-완전(NP-complete) 문제라고 한다. NP 문제들 중에 풀 수 있는 가장 어려운 문제라고도 할 수 있다.