알고리즘의 효율성

CS/알고리즘

알고리즘의 효율성

hyehh 2023. 10. 25. 21:54

728x90

SMALL

728x90

SMALL

알고리즘의 효율성

01. 알고리즘의 수행시간

1. 알고리즘을 통한 문제 해결

1. 수학에서는 문제를 풀기 위해 정의나 정리들을 활용

2. 컴퓨터에서는 문제해결을 위해 알고리즘 이용

3. 문제를 철저하게 분석한 후 알고리즘을 거쳐 프로그램 작성

2. 바람직한 알고리즘

1. 명확해야 한다.

- 이해하기 쉽고 가능하면 간명(간단명료)하도록 해야 한다.

- 지나친 기호적 표현은 오히려 명확성을 떨어뜨린다.

- 명확성을 해치지 않으면 일반 언어의 사용도 무방하다.

왜 명확해야 되냐?

결국 알고리즘은 컴퓨터로 프로그래밍해야 된다. 그렇기 때문에 모호하거나 분명하지 않는 내용이 있으면 이것을 프로그램화할 수 없다. 만약 프로그램화했더라도 제대로 된 결과를 만들어낼 수 없다.(계산해 낼 수 없다.)

2. 효율적이어야 한다.

같은 문제를 해결하는 알고리즘들의 수행 시간이 수백만 배 이상 차이 날 수 있다.

가능하면 수행시간이 짧아야 된다.

3. 알고리즘 공부의 목적

알고리즘은

문제 해결 절차를 체계적으로 기술한 것

알고리즘 공부의 목적은

특정한 문제를 위한 알고리즘의 자체를 습득하는 것도 있고,

체계적으로 생각하는 훈련을 하는 것도 있고,

지적 추상화의 레벨 상승을 위한 것도 있다.

결국 미래에 또 다른 어떤 문제를 해결하기 위한 기초가 되는, 생각의 훈련, 생각을 틀을 만드는 기반을 배운다. 는 것이다.

같은 문제에서도 효율이 아주 큰 차이가 나는 다양한 알고리즘이 존재한다.

이들에 대해 학습하는 과정에서 얻을 수 있는 여러 가지 기법과 생각하는 방법도 중요하다.

4. 알고리즘 분석의 필요성

바람직한 알고리즘은 명확하고 효율적이어야 한다.

알고리즘을 만들면 거기서 끝이 아니다. 평가를 해야 된다. 이 알고리즘이 에러 없이 잘 동작하는지, 원하는 결과를 정확히 계산하는지, 또 유의미한 시간 안에 계산 결과를 계산해 내는지 등 이런 분석이 반드시 필요한다.

알고리즘을 설계하고 나면

이 알고리즘이 자원을 얼마나 소모하는지 반드시 분석해야 한다.

# 자원이라는 것은

소요하는 시간, 메모리를 얼마나 차지하는가, 이 알고리즘이 수행이 되면서 발생하는 통신 대역이 얼마나 발생하는지 등

어떤 알고리즘이 문제를 해결하는데 굉장히 많은 입출력이 발생이 되어서

메인메모리를 자주 참조하고 다시 읽고 쓰고 이런 과정을 너무 반복한다던지 이랬을 때에는 효율성이 떨어질 수 있다.

효율성을 분석할 때 뭐를 가장 중요하게 여겨야 되느냐?

메모리를 가장 적게 사용하는 것을 가장 좋은 알고리즘으로 평가할 것이냐?

또는 통신 트래픽을 덜 발생시키는 것을 좋은 알고리즘으로 평가할 것이냐?

아니면 시간이 적게 걸리는 알고리즘을 좋은 알고리즘으로 평가할 것이냐?

이것들을 우리가 판단해야 된다.

현재 우리가 일반적으로 가장 중요하게 생각하는 것은?

소요시간을 가장 중요하게 생각한다.

자원의 가장 중심 대상은 소요시간

일반적으로 시간의 분석은 최악의 경우와 평균적인 경우에 대한 분석이 대표적이다.

근데, 분석 방법에는 최악의 경우와 평균적인 경우, 최선의 경우 3가지가 있다.

# 최악의 경우 : 어떤 작업을 하는데, 이 작업을 상사가 물어본다.

"그 작업 언제까지 끝낼 수 있어요?"

"아무리 늦어도 1시간 안에 끝낸다." 이 경우는 최악의 경우이다.

그러면 상사가 생각했을 때 이 작업은 최대한 1시간 안에는 끝나는구나 가장 많이 걸려봤자 1시간이구나 이것을 알 수 있기 때문에 최악의 경우가 의미가 있다.

# 평균적인 경우 : 해결해야 하는 문제가 3개가 있는데 각각 하나는 20분 걸리고 하나는 50분 걸리고, 하나는 40분 걸린다.

작업이 각각 끝낼 때 3개 작업의 평균을 구할 수 있다.

그렇기 때문에 최악의 경우와 평균적인 경우가 대표적으로 사용된다.

이 두 가지 중에서도 최악의 경우를 더 많이 고려한다.

# 최선의 경우 : 의미는 있기는 하지만 중요하다고 생각하지는 않는다.

왜냐하면 어떤 작업을 할 때 어떤 작업은 20분 만에 끝나고, 어떤 작업은 30분 만에 끝나고, 어떤 작업은 2시간이 걸린다.

그랬을 때 이 3가지 작업 중에 가장 빨리 끝난 작업은 20분 작업이다.라고 말할 수는 있지만, 가장 최선의 시간 분석은 사실 알고리즘을 분석하는 데에서는 크게 의미를 두지는 않는다.

시간 분석을 하면 알고리즘이 어느 정도의 입력에서 어느 정도의 시간이 필요한지 미리 짐작 가능하다.

그렇기 때문에 주어진 시간에 요구하는 작업이 완료 가능한지를 알 수 있다.

실제로 어떤 프로그램이 있다고 했을 때 프로그램으로 작성된 것을 분석하는 것이 절대로 아니다.

프로그램을 작성하기 전에 프로그램을 간단하게 표현한 알고리즘, 이것의 수행시간을 분석하는 것이다.

그렇기 때문에 이 알고리즘에서 입력데이터가 100개일 때 얼마큼의 시간이 걸린다고 하면

그러면 실제 프로그램에서 입력이 1,000개, 5,000개일 때를 따져야 된다. 그랬을 때 이 알고리즘이 얼마만의 시간이 걸리느냐를 예측할 수 있다면 그다음에 주어진 시간 안에 요구하는 작업이 끝날 수 있는지, 완료할 수 있는지 없는지를 판단할 수 있는 근거가 된다. 그래서 시간 분석, 소요하는 시간 분석이 굉장히 중요하게 다뤄지고 있다.

5. 알고리즘의 수행시간

알고리즘의 수행 시간은

입력의 크기에 대해 시간이 어떤 비율로 소요되는지로 표현된다.

입력의 크기

1. 정렬의 경우 정렬하고자 하는 개체의 수

2. 도시 간의 거리를 구하는 경우 계산에 관여되는 도시의 총수와 도시 간 간선(도로)의 총수

3. 계승을 구하는 경우에는 계승치를 구하고자 하는 자연수의 크기

4!(4팩토리얼), 100!(100팩토리얼) 이렇게 팩토리얼 계산을 우리가 할 수도 있다.

계승을 구하기 위한 문제일 경우에는 팩토리얼을 계산하기 위한 계승치,

4팩토리얼, 100팩토리얼을 계산하고자하는, 구하고자하는 자연수의 크기가 입력의 크기 된다.

입력값 n에 따른 알고리즘 수행 시간

읽는 방법 : O는 Order의 머리글자

O(n)의 경우 'n의 오더' 혹은 '오더 n' 이라고 읽으며 된다.

O(1)

Big-O 표기법으로 표현한 것으로 시간복잡도를 표현한 것이다.

알고리즘의 수행시간 o(1)이라고 하는 것은 한 번에 이 작업이 끝나는 것이다.

일정한 상수 시간 안에 이 작업이 끝나는 것이다. 굉장히 짧은 시간이다. 가장 수행시간이 적게 걸리는 것이다.

O(log2 n)

log시간만큼 증가된다. 입력 데이터 n2값이 증가되면서 log n만큼의 어떤 일정한 값에 일정한 시간이 걸리는 경우로

log시간이 O(1) 보다 더 수행시간이 많이 걸린다.

O(n)

n의 개수에 따라서 선형적으로 O(n)이니깐 일차 함수이다.

선형시간이 걸리는 경우로 O(log2n) 보다 더 수행시간이 많이 걸린다.

O(nlog2n)

log에 선형시간 만큼

O(n) 보다 더 수행시간이 많이 걸린다.

O(n^2)

제곱시간으로 그 다음 많이 걸리는 시간

O(nlog2n) 보다 더 수행시간이 많이 걸린다.

O(2^n)

좋은 알고리즘은 아니다. n의 개수가 엄청 크지 않더라도, n의 개수가 백만 되더라도 2의 100승이 되기 때문에 굉장히 많은 숫자값이 나온다. 그렇기 때문에 좋은 알고리즘이 아니다.

뒤로 갈수록 좋은 알고리즘이 아니다.

그만큼 시간이 많이 걸린다는 것이다. 그래서 알고리즘에 수행시간을 크기 비교로 나타낼 수 있다.

수행 시간의 포함 관계

이렇게 포함 관계를 표현할 수 있다.

30분이면 끝나는 작업을

1시간 안에 끝난다. 이렇게 이야기해도 틀리지 않는다.

5시간 안에 끝난다. 이렇게 이야기해도 틀리지 않는다.

그렇기 때문에 포함관계가 된다.

30분이라는 것은 1시간 안에 포함이 되고, 5시간 안에 포함이 된다.

이런 포함 관계를 표현한 것이다.

O(1)

O의 n승 예를 들어서 한 번 걸린다. O(1)

14번 수행된다. 1000번 수행된다. 상수번이다. 상수번 수행될 때 보통 O(n)번 수행한다라고 되어 있는데,

이거는 O(logn) 안에 포함이 된다라고 할 수 있다.

즉, 상수번 수행되는 알고리즘을 O(logn)만큼 걸린다.라고 할 수 있다.

20분 걸리는 문제를 1시간 안에 끝난다.라고 표현할 수 있는 것처럼

O(1) 보다 더 큰 개념으로 표현이 될 수 있다. 마찬가지로 O(logn)은 O(n)에 포함이 된다라고 할 수 있다.

O(n)은 예를 들어서

5n+4 형태

O(n) 보다 더 큰 개념은 O(n^2)이 된다.

예를 들어서 2n2 + 10n +3 만큼의 시간이 걸린다라고 했을 때 big-O표기법으로 표현을 하면 O(n^2)으로 표현할 수 있다.

그래서 O(n^2)로 표현하는 것은 이 안에는 O(n)도 포함되고, O(logn)도 포함되고 O(1)도 포함이 되는 것이다.

그다음에 O(n^3)이나 O(n^k)

k는 n의 지수승, n의 4승, n의 5승, n의 10승을 뜻한다.

이런 해당되는 시간복잡도는 안의 내부들을 포함한다.

가장 시간복잡도가 많이 걸리는 O(2^n)

애는 n의 크기가 조금만 커지면 기하급수적으로 늘어난다. 엄청나게 많은 수행시간을 갖게 되기 때문에 효율적이지 않은 알고리즘이다. 그래서 O(2^n) 같은 경우에는 모든 big-O 표기법에 있는 내부적인 것들을 다 포함하고 있다.

그래프로 표현한 것

x축은 n의 개수이다.

입력자료의 수

y축은 수행시간이다.

얼마나 많이 걸리냐

개수가 많아질수록 수행시간이 많이 걸린다.

그런데, 데이터가 적을 때에는 그렇게 시간차이가 나지 않는다.

그래서 가능하면 수행시간이 적게 걸리는 게 효율적인 알고리즘이다.

실제로 대입한 결과

n의 값이 조금만 커지면 수행시간이 엄청나게 차이가 난다.

n은 입력데이터이다.

function 수행시간에 대한 부분이다.

O(1) 상수시간이 걸린다고 했을 때 입력데이터가 10개이던, 100개이던 1,000개이던 다 한 번에 끝난다.

상수시간만큼만 걸리고 끝난다. 이런 경우에는 굉장히 간단하고 수행시간이 짧게 걸리는 알고리즘이라고 할 수 있다.

log2n

n이 10이면 3만큼 걸리고 100이면 6만큼 걸린다. 이 정도도 뭐 수행시간이 많이 걸리지 않아 좋은 알고리즘이라고 할 수 있다.

n인 경우에는 n에 개수에 따라서 값이 달라진다. 10일 때는 10만큼 걸리고 100일 때는 10의 2승만큼 걸린다.

n * lon2n

입력데이터가 10일 때는 30만큼, 100일 때는 664만큼 뭐 이 정도도 나쁘지 않다.

어느 정도 효율적인 알고리즘이라고 이야기할 수 있다.

n^2

그러나 n을 제곱하게 되면 수행시간이 기하급수적으로 늘어난다.

데이터를 10개 넣었더니 10의 제곱만큼 수행시간이 걸리고 100일 때는 10의 4승만큼

n^3

3승이니깐 2승보다 더 수행시간이 늘어난다.

2^n

가장 나쁜, 가장 효율이 안 좋은 2의 n승이다.

우리는 현재 빅데이터시대에 살고 있는데, 데이터가 개수가 100만 개도 많은 게 아니다. 우리는 현재 수조데이터를 활용하고 있는 시대에 살고 있다.

알고리즘의 수행시간을 좌우하는 기준

1. for 루프의 반복 횟수

대표적인 기준으로 for 루프가 있다.

계속 반복이 된다는 것은 그만큼 for 루프 안에 있는 덧셈이나 뺼셈이나 연산이 계속 반복이 된다는 것이기 때문에 for 루프의 반복 횟수가 얼마냐에 따라서 수행시간이 결정된다.

2. 특정한 행이 수행되는 횟수

특정한 행이 몇 번 수행이 되느냐?

예를 들어서 for 루프 안에 어떤 명령문이 있는데, 그 명령문이 for문이 반복되면서 몇번 수행되느냐?

수행되는 횟수를 말한다.

3. 함수의 호출 횟수

어떤 임의의 함수가 계속 프로그램 안에서 호출이 된다라고 했을 때

이 함수가 호출되는 횟수를 말한다.

이런 것들이 알고리즘의 수행시간을 좌우하고 판단하는 기준이 된다.

등등..

전체 데이터중에서 중간번쨰에 있는 데이터를 찾는 알고리즘이다.

즉, 10개의 데이터를 입력해 주고 그중 가운데에 있는 5번째에 있는 데이터를 찾는 것이다.

배열에 들어가는 실제 데이터의 개수

k는 n/2

어떻게 할 수 있느냐?

일단 2분의 n이기 때문에

100개면 2분의 100 해서 50번째를 계산하면 된다. 그러면 데이터 50이 인덱스이다.

가운데에 있는, 전체 데이터 배열중에서 인덱스가 50인 것

중간에 있는 데이터를 return 해주는 것, 반환해 주는 것이다. 그렇게 하고 끝이 난다.

몇 번 수행이 될까 생각할 수 있다.

int k는 2분의 n이다.

n이 얼마가 됐든, 100이든, 1,000이든, 5,000,000이든 이것을 2분의 n을 한다.

반으로 나누는 연산 딱 한 번 하고 대입한다. 이 결과를 return data[k]에 대입한다.

즉, 대입연산: 1번, 나누기 연산 : 1번이 이루어진다.

그렇기 때문에 이것은 1+1

최종적으로 2번 걸린다. 이만큼의 수행시간이 걸린다고 할 수 있다.

그러면 n에 관계없이 상수 시간이 소요되기 때문에 이 경우 알고리즘의 시간복잡도는 o(1)이 되는 것이다.

근데, 대입연산 1번, 나누기 연산 1번이니깐 o(1)이 아닌 o(2) 아님???

이것도 틀린 이야기는 아니다. 근데 일반적으로 일정한 상수시간이 걸린다라고 했을 때에는

이것을 그냥 o(1)만큼 걸린다라고 이야기한다.

왜냐하면 사실 알고리즘에서는 정확하게 프로그램을 짠 상태에서 프로그램 자체가 얼마큼 걸리는지 분석하는 게 아니다.

프로그램을 만들기 직전에 알고리즘을 작성한 다음에 이게 정확한 값이 아닌 대략적으로 얼마큼 걸리는지의 근삿값을 계산하는 것이기 때문이다.

이 데이터에 있는 모든 값들을 더하는 알고리즘이다.

데이터라는 배열이 주어지고,

n이라는 데이터 개수가 입력으로, 매개변수로, 인수로

sample이라는 함수가 실행이 된다.

int sum이라는 변수에 0이라는 값을 저장한다. 이 문장은 한 번 수행된다.

초기값을 쥐어준다.

for문 반복문이다. int i는 0부터, i는 n보다 작은 동안에 밑에 있는 문장을 수행하라 (sum = sum + data[i])

이 알고리즘에서 가장 자주 실행되는 문장은 for 루프 안에 있는 빨간 네모박스 문장이다.

i가 0부터 n보다 작을 때 동안이니깐 결국엔 n-1번째까지라고 이해할 수 있다.

0부터 n-1번까지 수행하니깐 실행 횟수는

n번이 된다. 즉, for문이 n번 수행된다.

그러니깐 for문 안에 있는 sum=sum+data[i]도 n번 수행이 된다.라고 할 수 있다.

그래서 하나의 어떤 알고리즘의 처음부터 끝까지 중에서 각각의 연산이 들어가 있는 문장, 대입이 되는 부분에 대해 실행 횟수, 수행 횟수를 계산했을 때 그중에서 가장 최악의 경우

가장 많은 수행시간이 걸리는 그 부분에 대한 수행시간이 이 전체 알고리즘의 수행시간이 될 수 있다.

내가 3가지 작업을 하는데, 각각 10분, 30분, 2시간이 걸릴 때 "너 그 작업 언제 모두 끝나?"라고 한다면

10분을 고려하지 않고 우리는 가장 worst case인 2시간을 말한다.

수행시간도 마찬가지로 전체 알고리즘에서 짧게 걸리는 부분들도 분명히 있지만, 그 부분은 알고리즘의 전체 수행시간을 얼마냐?라고 판단할 때 그 부분은 무시해도 되기 때문에 가장 많이 수행되는 곳 그곳의 수행 횟수를 따진다.

가장 많이 실행되는 문장의 수행시간이 n번이기 때문에 모든 문장의 실행 횟수의 합은 n에 선형적으로 비례한다고 할 수 있다다.

모든 연산들의 실행 횟수의 합도 역시 n에 선형적으로 비례한다고 할 수 있다.

이 알고리즘을 수행할 때 각각 한 줄 한줄 몇 번 수행되는지 판단해 보자

sum= 0 : 대입하는 연산이 1번 수행되었다.

sum= sum + data[i] 이 부분에서 대입하는 연산 몇 번 하느냐? for문이 반복되는 횟수만큼 즉 n번 수행된다.

그러면 대입하는 연산은 n+1번 수행된다.

덧셈하는 연산은 for문의 반복 횟수와 동일하다.

n번 수행된다.

그러면 이 알고리즘에서는 대입연산 n+1번이랑 덧셈연산 n번이 걸린다.

이 두 개를 더하면 (n+1)+(n) = 2n+1이 나온다.

그러면 이것을 복잡도로 말할 때 o(2n+1)만큼이라고 할 수도 있지만 big-o표기법으로 했을 때

상수 부분은 별로 전체 수행시간에서 크게 좌우되는 것이 아니기 때문에 상수식(+1)은 제외한다.

그리고 또 어떤 변수라고 생각한다면 변수의 개수(2)도 크게 고려하지 않는다

그래서 최고차항만을 따져서 o(n)만큼의 시간복잡도를 갖는다라고 이야기를 한다.

이런 식으로 수행시간을 계산할 수 있다.

중복 for문

for루프 안에 또 for루프가 내포가 되어있다.

대입연산: n^2 + 1번

sum=0 대입연산 1번 수행되었다.

sum =sum + A[i]*A[j] 은

첫 번째 for문 i <=n 까지니깐 1부터 n까지임으로 n번 수행된다.

두 번째 for문 i <=n 까지니깐 이것도 n번 수행된다. 그렇다는 건 sum = sum에 해당하는 대입연산은 n 곱하기 n번 즉 n의 제곱만큼 수행됨을 알 수 있다.

덧셈연산: n^2번

sum + a[i]

첫 번째 for문과 두 번째 for문의 수행 횟수만큼 즉 n의 제곱만큼 수행된다.

곱셈연산: n^2번

A[i] * A[j]

애도 마찬가지로 n의 제곱만큼 수행된다.

그래서 이 전체 알고리즘이 수행되는데 드는 시간은

대입연산과 덧셈연산 곱셈연산의 횟수를 차례로 더한다. 3n^2+1만큼 걸린다.

o(3n^2+1) 이런 식으로 표현할 수 있지만 상수에 해당되는 부분과 최고차항의 계수 부분을 제외하고 최고차항만 표현한다.

그래서 o(n^2)만큼 수행시간이 걸린다.라고 할 수 있다.

6. 재귀적 (Recursive) 알고리즘

재귀 = 자기 호출

자기 자신을 호출한다.

재귀적 사고

해법을 알고 그것을 반복적으로 적용하는 것이다.

어떤 문제 안에 크기만 다를 뿐 성격이 똑같은 작은 문제들이 포함되어 있는 것

이것을 재귀적 알고리즘이라고 이야기한다.

병렬화 개념은 하나의 일을 나누어 동시에 병렬로 처리

병렬은 똑같은 작업을 여러 군데에서 한다라는 의미이다.

똑같은 작은 단위로 이루어진다. 그렇기 때문에 이것도 재귀적 알고리즘으로 작성할 수 있다.

재귀적 알고리즘에 해당하는 것

1. 팩토리얼

5!(5팩토리얼) = 5 x 4 x 3 x 2 x 1 이거는 사실 5 x 직전에 해당하는 4팩토리얼 5 x 4!이렇게 계산할 수도 있다.

또 4패토리얼도 3팩토리얼을 넣는다. 사이즈만 작아질 뿐 똑같은 동작이 계속 반복이 된다.

그렇기 때문에 팩토리얼이라는것도 재귀적 알고리즘으로 작성할 수 있다.

2. 수열의 점화식

수의 일정한 나열을 수열이라고 한다.

수의 일정한 나열에는 일정한 규칙이 있다. 예를 들어서 앞의 항에 일정한 값 2를 더하면

1 3 5 7 9... 이런 식으로 계속 나온다. 이것은 앞에 항에 +2라는 동작이 계속 반복이 된 것이다. 이것을 점화식으로 표현해서

a의 n항은 a의 n-1에 +2라고 쓸 수 있다. 전체 중에서 어떤 임의의 항은 바로 직전항에다가 2만큼을 더했다. 이런 수열의 경우에는 이렇게 표현할 수 있다. 그렇다는 것은 이런 수열에 점화식을 표현한다는 것은 n번째를 계산하기 위해서 직전에 해당이 되는, 크기만 작아졌지 똑같은 동작을 반복하는 것이다. 그렇기 때문에 재귀적 알고리즘이라고 할 수 있다.

3. 피보나치

계속해서 앞의 수에다가 뒤에 수를 더해서 그다음 수가 나오는 것이기 때문에 재귀적 알고리즘을 작성할 수 있다..

4. 병합 정렬

전체의 정렬 데이터를 반으로 나눠서, 정렬하고

반으로 나뉜 정렬 데이터를 또 반으로 나눠서 또 정렬해 가는 과정을 반복하기 때문에 재귀적 알고리즘을 작성할 수 있다.

등등

02. 알고리즘의 효율성 분석

1. 알고리즘의 분석

알고리즘의 자원 (Resource) 사용량을 분석한다.

자원이란 실행 시간, 메모리, 저장장치, 통신 등

여기서는 실행시간의 분석에 대해서 다룬다.

일반적으로 알고리즘 분석을 할 때 실행시간을 가장 중요하게 여긴다.

2. 알고리즘의 복잡도 (Complexities of Algorithm)

여러 알고리즘 중 처리 시간이나 차지하는 메모리 용량이 적은 알고리즘이 프로그램 효율성도 높다.

알고리즘을 어떤 식으로 작성하느냐에 따랄 실행되는 시간과 공간이 다르며 이것을 알고리즘의 복잡도라고 한다.

알고리즘 성능분석은 2가지로 나눌 수 있다.

1. 성능 측정 : 실제 구현 필요 구체적으로 실행시켜 시간을 확인

성능 측정 방법은 구현해야 하므로 잘 안 쓴다. 그렇지만 구현해야 하기 때문에 정확한 방법이다.

2. 성능 분석: 구현 불필요

시간 복잡도 : 입력 개수(n)에 따른 실행 횟수

공간 복잡도 : 메모리 공간을 얼마나 차지하느냐?

n이 4개일 때 n^2은 16초가 걸린다. 2^n도 16초이다.

아무리 복잡도가 큰 알고리즘이라고 하더라도 데이터 개수가 적으면 수행시간이 큰 차이가 안 난다.

그런데 n이 커질 때 임의의 데이터개수가 100개면 많은 개수가 아니다. 100개일 때를 예를 들면

n^2이다라고 하면 만초가 걸린다. 2^n초일 때에는 엄청난 시간이 걸린다.

이러한 복잡도를 가지는 알고리즘은 바람직한 알고리즘이 아니다.

효율적이라고 생각할 수 없다.

시간복잡도와 공간복잡도가 있다.

일반적으로 알고리즘들을 비교할 때에는 시간복잡도가 주로 사용된다.

알고리즘의 복잡도는 처리해야 하는 데이터의 양이나 표현 방법, 컴파일러 등에 따라 달라지므로 성능 측정이 어렵다.

입력 데이터가 많을수록 실행 속도나 성능이 저하되므로 입력 데이터가 무한히 많아질 때의 알고리즘의 성능을 주로 평가한다.

3. 시간 복잡도

실행시간은 실행환경에 따라 달라진다.

하드웨어, 운영체제, 언어, 컴파일러 등

실행시간은 환경에 따라 달라지기 때문에 실행 시간을 측정하는 대신에

연산의 실행 횟수를 카운트를 해서 복잡도를 계산한다.

연산의 실행 횟수는

입력 데이터의 크기에 관한 함수로 표현한다.

데이터의 크기가 같더라도

실제 데이터에 따라서 달라진다.

시간복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현

예) 10장의 숫자 카드 중에서 최대 숫자 찾기

순차탐색으로 찾는 경우에 숫자 비교가 기본적인 연산이고, 총 비교 횟수는 9 임

n장의 카드가 있다면, (n-1) 번의 비교 수행이 된다. 그렇기에 시간 복잡도는 (n-1)으로 표현된다.

big-o표기법으로는 o(n)만큼 걸린다라고 표현할 수 있다.

알고리즘의 복잡도를 표현하는 데는 다음과 같은 분석 방법들이 있다.

1. 최악의 경우 : 시간 분석(Worst Case Analysis)

2. 평균의 경우 : 분석(Average Case Analysis)

3. 최선의 경우 : 분석 (Best Case Analysis)'

알고리즘 속도에서 우리는 이 3가지를 따지는데, 사실은 가장 의미 있게 판단하는 것은 최악의 경우이다. 그다음에 평균의 경우를 일반적으로 다루고 있다. 물론 최선의 경우도 필요한 경우가 있지만, 알고리즘이 얼마큼 걸리느냐에 대해서 가장 빠르게 걸리는 경우는 이 알고리즘을 분석하는 데에는 크게 의미가 없다.