[알고리즘]시간 복잡도란?

자료구조와 알고리즘을 배울때 핵심 :  공간 , 시간 이용

(공간과 시간은 거의 항상 반비례하는 경향이있다)

시간복잡도: 어떤 알고리즘이 얼마나 걸리느냐(CPU사용량)

공간복잡도: 어떤 알고리즘이 메모리를 얼마나 쓰느냐(RAM사용량)

Related works

2.1 시간 복잡도 나타나는 수

중요한 시간들 in algorithm

1(constant) : 입력자료의 수에 관계없이 일정한 실행시간 갖음

Log N : 입력자료의수에 따라 시간이 점점 시간이 조금씩 증가함 - 주로 큰 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형. 예) 효율이 좋은 검색 알고리즘.. 이 뭐가 있드라. 이진탐색 같은 것 - Log_­2n

N(Linear) : 입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우- 입력자료 각각에 일정량(시간)이 할당되는 경우

N Log N :  이것은 주로 큰문제를 일정한 크기를 갖는 문제로 쪼개고(Log N), 다시 그것들을 하나로 모으는 경우에 나타남 (N). 예) 효율 좋은 정렬 알고리즘.. quick sorting, heap sorting 등. link: http://wrice.egloos.com/3097929

N² :  이중루프내에서 입력자료를 처리할때 발생함. 

N³ :  얘는 삼중 루프내에서 입력 자료 처리할때 발생. 

※ 알고리즘에서 가장 기본이 되는 것은 정렬과 검색임 !!!

2.2 시간 복잡도란?

시간 복잡도  = 알고리즘을 구성한 명령어가 실행된 횟수(frequency of calling command)

(+ execution time 인데, h/w 의존하기 때문에 일단 이것은 제외함) 

주로 시간과 공간의 반비례하는데, 요즘에는 시간이 우선 !!! ( because of h/w tech was improved)

2.3 시간 복잡도 표현(Notation)

Big O - O(N) : 실행 시간 상한 표현 (가장 많이 쓰임) - 최악의 시간 계산 

Ω      - Ω(N) : 실행 시간 하한 표현                         - 운좋을때 걸리는시간

Θ      - Θ(N) : 실행 시간 평균 표현 

2.4 시간의 복잡도 계산법

명령이 끝날때마다 실행 횟수를 적어봅니다.

명령어 실행횟수를 모두 더하면 2n²-2n+2  ->상수는 생략하고 최고차항만 생각한다. => O(n²)로 표기합니다.

재귀함수 시간 복잡도 계산법

앞선 방법 처럼 쉽게 구해지지 않은다. ( 우선 재퀴호출이 없다면 상수시간 소요됨 )

따라서, 재귀 호출이 불리는 횟수가 수행 시간을 좌우한다. 

Factorial(n) -> Factorial(n -1) .... ->Factorial(2) -> Factorial(1) 

이 경우 n번 호출 됨으로 O(n)으로 표기 

n>1

T(n) = T(n-1) +T(n-2) + C

O(2ⁿ)  > T(n)= Θ(1.6ⁿ) > Ω(2^n/2)

안좋은 이유 : 중복되는 Fibonacci(2)를 3번이나 계산하게됨. 

ref :http://www.youtube.com/watch?v=pqivnzmSbq4   

따라서 피보나치는 아래와 같이 반복문을 사용해서 개선할 수 있다. 

으로 O(n)이다. 음.. 이건  어짜피 이건 무조건 돌아야 되니까 O(n) = Θ(n) =  Ω(n) 이다. 

따라서, 피보나치는 반복 알고리즘이 더 재귀보다  성능이 좋음을 알려주는 하나의 예이다. 

하지만, 항상 재귀가 나쁜것은 아니다 -> 설계단계에서 재귀 알고리즘 매우 유용하다.