자료구조 공부 알고리즘의 복잡도 분석 방법

http://blog.naver.com/wlsgkr91/220901179608 

1. 알고리즘의 복잡도 분석 방법.

-여러 가지 문제점 때문에 구현하지 않고 알고리즘의 효율성을 따져보는 기법이 알고리즘의 복잡도 분석이다. 

-알고리즘 복잡도 분석은 구현하지 않고도 모든 입력을 고려하는 방법이고 실행 하드웨어나 소프트웨어 환경과는 관계 없이 알고리즘의 효율성을 평가할 수 있다. 

2.시간 복잡도 함수

-알고리즘의 실행 가능 분석을 시간 복잡도 라고 하고알고리즘이 사용하는 기억 공간 분석을 공간 복잡도라고한다.

-시간 복잡도는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 

실행되는지를 숫자로 표시한다. 

ex)만약 동일한 조건에서 똑같은 일을 하는데 알고리즘1이 20개의 연산을 실행, 알고리즘 2가 100개의연산을 실행하였다면 당연이 알고리즘 1이 알고리즘 2에 비하여 실행하는 연산의 수가 적으므로 더 효율적인 알고리즘 이라고 할 수 있다. 이것이 시간 복잡도 방법의 기본 개념.

3.빅오 표기법

-보통 시간 복잡도 함수에서 중요한 것은 n이 증가하였을 때연산의 총 횟수가 n에 비례하여 증가하는지, 아니면 n의2에 비례하여 증가하는지 , 아니면 다른 증가 추세를 가지는 지가 더 중요하다.

-시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법 이라고 한다. O(n) ="빅오 of n"

두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>=n0에 대하여 |f(n)| <=c|g(n)|을 만족하는 2개의 상수 c와 n0이 존재하면 f(n)=O(g(n))이다. 

ex)

f(n)=5이면 O(1)이다.

f(n)=2n+1이면 O(n)이다.

f(n)=3n^2+100이면 O(n^2)이다.

f(n)=5*2^n+10^2이면 O(n^2)이다. 

-빅오 표기법을 얻는 간단한 방법은 기본 연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차 항만을 남기고다른 항들과 상수항을 버리는 것이다. 

실행시간이 빠른 순서

상수<로그<선형<선형로그<2차형<3차형<지수형<팩토리얼

4.빅오 표기법 이외의 표기법

1.빅오메가 표기법

두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>=n0에 대하여 |f(n)| <=c|g(n)|을 만족하는2개의 상수 c와 n0이 존재하면 f(n)=Ω(g(n))이다. 

2.빅세타 표기법

두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>=n0에 대하여 c1|f(n)| <=c2|g(n)|을 만족하는 3개의 상수 c1와 c2와 n0이 존재하면

f(n)=θ(g(n))이다. 

5.최선,평균,최악의 경우

-알고리즘의 효율성은 주어지는 자료의 집합에 따라 다음의 3가지 경우로 나누어서 평가할 수 있다. 

1.최악의경우는 자료 집합 중에서 알고리즘의 실행 시간이 가장 오래걸리는 경우이다.2. 최선의 경우는 실행 시간이 가장 적은 경우를 의미한다. 3.평균적인 경우는 알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균적인 실행 시간을 의미한다. 

-3가지 경우 중에서 평균적인 실행 시간이 가장 보이나, 평균 실행 시간을 산출하기 위해서는 광범위한 자료 집합에 대하여 알고리즘을 적용시켜서 평균값을 계산해야 한다. 

따라서 평균 실행 시간은 상당히 구하기 힘들 수도 있다.

따라서 최악의 경우의 실행시간이 알고리즘의 시간 복잡도 척도로 많이 쓰인다. 최악의 경우란 입력 자료 집합을 알고리즘에 최대한 불리하도록 만들어서 얼마만큼의 시간이 소모되는지를 분석하는 것이다. 최선의 경우는 알고리즘에 따라서 별 의미가 없는 경우가 많다. 

자료 구조 표기법은 typedef의 사용을 하는데 이는 구조체의 공부를 필요로 한다.

 자료구조에 관련된 데이터에서 C언어는 객체지향 언어가  아니기때문에 하나의 구조체에 관련된 자료들을 넣어 함수를 호출할 때마다 이 구조체의 포인터를 전달하는 것이다. 이렇게 하면 어느 정도 관련된 자료를 모아서 함수로 전달할 수 있어서, 전역 변수를 사용하지 않아도 작업이 가능해진다. 구조체 그 자체를 전달하는 것이 아니라 사실은 구조체에 대한 포인터를 전달하여야 한다. 그래야만 구조체를 함수 내에서 변경할 수 있다.