[알고리즘 문제 해결 전략] 02 알고리즘 분석 - 알고리즘 시간 복잡도 분석 review

알고리즘 : 문제를 해결하는 한 가지 방법을  명료하게 써 놓은 것

소스코드 != 알고리즘

명료하고 모호하지 않은 형태로 표현하기 위해 대체로 소스코드의 형태로 설명하기에 둘이 비슷해 보일 수 있지만 알고리즘은 문제를 해결하는 방법 그 자체이며 완전히 달라 보여도 같은 원리에 따라 동작한다면 같은 알고리즘을 사용한다고 할 수 있다.

한 문제를 해결하는 여러 알고리즘 중에 어떤 것을 배워야 할까?

알고리즘의 평가 기준 

1. 시간 : 알고리즘의 수행 속도와 특성을 분석하는 능력을 키울 필요가 있다.

2.공간 : 알고리즘이 아무리 빠르더라도 너무 많은 메모리 공간을 요구한다면 수행 x

두 기준은 서로 상충할 때가 많다. 

대회에서는 주로 속도를 중요시한다.

 

알고리즘의 시간 복잡도 분석

프로그램의 실행시간은 알고리즘의 속도를 이야기하기에는 부적합하다. 운영체제,언어,컴파일러 등 다양한 요소에 영향을 받기 때문이다.

한 가지 항목이 전체의 대소를 좌지우지하는 것을 지배한다(dominate)고 표현한다.

ex)  서울에서 부산까지 타고갈 것을 정할때 시동걸리는 데 걸리는 시간보다 시속이 더 중요하다.

시속이 이동시간을 지배한다.

 

알고리즘의 수행시간을 지배하는 것은 반복문

입력의 크기가 커지면 커질 수록 반복문이 알고리즘의 수행 시간을 지배한다.

 

N일 동안 M-이동평균을(몸무게) 구하는 방법 (M-1일부터 이동평균을 계산할 수 있다.)

방법 1: M일 측정치를 더하고 M으로 나눈다.

단점: 매일매일 다시 계산해야한다.

방법 2 :  M일의 이동평균과 M-1일의 이동평균은 0과 M일의 몸무게를 제외하고 같은 숫자가 포함된다.

M-1일의 이동평균에 사용되는 몸무게 -(0일째 몸무게)+(M일째 몸무게)=M일의 이동평균에 사용되는 몸무게 

방법 2의 알고리즘의 수행시간은 N에 정비례한다.

입력의 크기 대비 걸리는 시간의 그래프가 직선일때 선형시간 알고리즘이라도 부른다.

 

입력의 크기가 커지는 것보다 수행시간이 느리게 증가하는 알고리즘들을 선형이하 시간 알고리즘이라고 한다.

ex)이진탐색

 

다항시간 알고리즘

반복문의 수행 횟수를 입력 크기의 다행식으로 표현할 수 있는 알고리즘

 

N^100도 다항시간 알고리즘이기 때문에 다항시간 알고리즘인 것 만으로 빠르다고 할 수 없지만 

다항시간보다 더더욱 오랜시간이 걸리는 알고리즘이 있다.

N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘들은 지수 시간에 동작한다고 말한다.

하지만 지수시간보다 빠른 알고리즘을 찾지 못한 문제는 널렸다.

그렇기 때문에 다항 시간과 지수 시간 사이의 경계는 현 전산학에서 효율적으로 해결할 수 있는 문제와 효율적으로 해결하는 방법을 아직 찾아내지 못한 문제이 경계 역할을 하고 있다.

 

시간복잡도

두 부호 있는 32비트 정수의 사칙연산

두 실수형 변수의 대소 비교

한 변수에 다른 변수 대입하기

위와 같은 기본적인 연산들은 더 쪼갤 수 없기 때문에 시간복잡도의 기준이 된다.

 

대부분의 경우 삽입 정렬이 선택 정렬보다 빠르다.

 

수행시간 어림짐작하기

어떤 알고리즘이 이 문제를 해결할 수 있을지 알기 위해서는 프로그램을 작성하기 전에 입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간을 어림짐작할 수 있어야한다.

입력크기와 시간복잡도를 알고있으면 알고리즘이 시간안에 동작할지 대락적으로 짐작가능하다.

프로그래밍 대회에서 사용하는 주먹구구 방법

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

 

시간 복잡도 외에 참조해야할 다른 요소

• 시간 복잡도가 프로그램의 실제 수행속도를 반영하지 못하는 경우
• 반복문의 내부가 복잡한 경우
• 메모리 사용패턴이 복잡한 경우
• 언어와 컴파일러의 차이
• 구형 컴퓨터를 사용하는 경우

P문제: 다항 시간 알고리즘이 존재하는 문제들의 집합 ex)정렬문제

계산 복잡도 클래스 : P문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합

NP문제는 다항시간에 풀 수 없는 문제가 아니다.

풀 수 없음을 증명하기 쉽지 않다.

NP문제란 답이 주어졌을 때 이것이 정답이지를 다항시간 내에 확인할 수 있느 문제를 의미

 

마스터 정리

재귀적인 알고리즘의 시간 복잡도를 곗나하는 쉬운 방법

소감: 어려운 내용이 많았다. 문제를 풀때 시간복잡도를 계산하면서 풀지 않았는데 앞으로 계산하면서 푸는 습관을 길러야겠다.

책 : 알고리즘 문제 해결 전략

저자 : 구종만