Complexity Analysis
Input size
For many algorithms, it is easy to find a reasonable measure of the size of the input, which we call the input size. For Example consider Sequential Search, Add Array Members, Exchange Sort, and Binary Search. In all these algorithms, n, the number of items in the array, is a simple measure of the size of the input. Therefore, we can call n the input size.
Example 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, 트리 구조에서 노드와 이음선의 수, 그래프 자료구조에서 정점과 이음선의 수 등
👉 많은 알고리즘에서 입력크기에 대한 합리적인 측정값을 쉽게 찾을 수 있다. 순차탐색, 교환정렬, 이진탐색 등의 경우 배열에 속한 아이템의 개수 n이 입력크기를 나타낸다.
Basic Operation
After determining the input size, we pick some instruction or group of instructions such that the total work done by the algorithm is roughly proportional to the number of times this instruction or group of instructions is done. We call this instruction or group of instructions the basic operation in the algorithm.
Example 비교(comparison), 지정(assignment)
👉 입력크기를 구한 후, 어떤 명령문(또는 명령문 군)을 선정하여 알고리즘이 수행한 총 작업의 양을 이 명령문(또는 명령문 군)을 수행한 횟수에 대략적으로 비례하도록 한다. 이때 이 명령문(또는 명령문 군)을 알고리즘의 단위연산이라고 한다.
Time Complexity
When analyzing the efficiency of an algorithm in terms of time, we do not determine the actual number of CPU cycles because this depends on the particular computer on which the algorithm is run. Furthermore, we do not even want to count every instruction executed, because the number of instructions depends on the programming language used to implement the algorithm and the way the programmer writes the program.
In general, the running time of an algorithm increases with the size of the input, and the total running time is roughly proportional to how many times some basic operation (such as a comparison instruction) is done. We therefore analyze the algorithm’s efficiency by determining the number of times some basic operation is done as a function of the size of the input. This is a standard technique for analyzing algorithms.
👉 시간을 기준으로 알고리즘의 효율성을 분석할 때, CPU의 실제 작동시간을 구하지는 않는다. 왜냐하면 그 결과는 알고리즘을 실행하는 특정 컴퓨터에 따라서 달라질 수 있기 때문이다. 더욱이 실행되는 모든 명령문의 개수를 세지도 않는데, 이는 알고리즘을 구현하는 프로그래밍 언어와 프로그래머의 코드 작성 방식에 따라서 명령문의 개수가 달라질 수 있기 때문이다.
일반적으로 알고리즘의 실행시간은 입력의 크기에 따라서 증가하고, 총 실행시간은 단위연산이 몇 번 수행되는가에 거의 비례한다. 따라서 단위연산이 수행되는 횟수를 입력의 크기에 대한 함수로 구하여 알고리즘의 복잡도를 분석한다. 이것이 알고리즘을 분석하는 표준 기법이다.
Memory(Space) Complexity
We have discussed only the analysis of the time complexity of an algorithm. All the same considerations just discussed also pertain to analysis of memory complexity, which is an analysis of how efficient the algorithms is in terms of memory.
👉 공간복잡도란 알고리즘이 메모리 사용 측면에서 얼마나 효율적인지를 분석하는 것이다. 시간복잡도 분석시 고려했던 모든 사항들이 공간복잡도 분석에도 그대로 적용된다.
Every-Case Time Complexity Analysis
T(n) is defined as the number of times the algorithm does the basic operation for an instance of size n. T(n) is called the every-case time complexity of the algorithm, and the determination of T(n) is called an every-case time complexity analysis.
Example Add array members
입력크기: n, 입력값: x(= 배열에 추가해야될 값)
모든 경우 시간복잡도 분석: T(n) = n
Example Matrix multiplication
입력크기: n, 입력값: x(= 행렬에 곱할 값)
모든 경우 시간복잡도 분석: T(n) = n
👉 T(n)은 입력크기 n에 대하여 알고리즘이 단위연산을 수행하는 횟수로 정의된다. T(n)은 알고리즘의 모든 경우 시간복잡도라고 하며, T(n)을 구하는 과정을 모든 경우 시간복잡도 분석이라고 한다.
이 분석은 입력크기 n에 종속되지만 입력값 x와는 무관하게 결과값은 항상 일정하다.
Worst-Case Time Complexity Analysis
W(n) is defined as the maximum number of times the algorithm will ever do its basic operation for an input size of n. So W(n) is called the worst-case time complexity of the algorithm, and the determination of W(n) is called a worst-case time complexity analysis.
Example Sequential Search
입력크기: n, 입력값: x(= 탐색을 통해 찾고자 하는 값)
최악의 경우 시간복잡도 분석 : W(n) = $n^{3}$
👉 W(n)은 입력크기 n에 대하여 알고리즘이 수행할 단위연산의 최대 횟수로 정의한다. W(n)은 알고리즘의 최악의 경우 시간복잡도라고 하고, W(n)을 구하는 과정을 최악의 경우 시간복잡도 분석이라고 한다.
이 분석은 입력크기 n과 입력값 x에 모두 종속되며, 단위연산의 수행 횟수가 최대인 경우를 선택한다.
Average-Case Time Complexity Analysis
A(n) is defined as the average (expected value) of the number of times the algorithm does the basic operation for an input size of n. A(n) is called the average-case time complexity of the algorithm, and the determination of A(n) is called an average-case time complexity analysis.
Example Sequential Search
입력크기: n, 입력값: x(= 탐색을 통해 찾고자 하는 값)
평균의 경우 시간복잡도 분석 : A(n) = (n + 1)/2
👉 A(n)은 입력크기 n에 대하여 알고리즘이 수행할 단위연산의 평균 횟수(기대값)로 정의한다. A(n)은 평균의 경우 시간복잡도라고 하며, A(n)을 구하는 과정을 평균의 경우 시간복잡도 분석이라고 한다.
이 분석은 입력크기 n과 입력값 x 모두에 종속되며 모든 입력에 대해서 단위연산이 수행되는 횟수가 평균이다. 일반적으로 최악의 경우 보다 계산이 복잡하다.
Best-Case Time Complexity Analysis
B(n) is defined as the minimum number of times the algorithm will ever do its basic operation for an input size of n. So B(n) is called the best-case time complexity of the algorithm, and the determination of B(n) is called a best-case time complexity analysis.
Example Sequential Search
입력크기: n, 입력값: x(= 탐색을 통해 찾고자 하는 값)
최선의 경우 시간복잡도 분석 : B(n) = 1
👉 B(n)은 입력크기 n에 대하여 알고리즘이 수행할 단위연산의 최소 횟수로 정의한다. B(n)은 알고리즘의 최선의 경우 시간복잡도라고 하며, B(n)을 구하는 과정을 최선의 경우 시간복잡도 분석이라고 한다.
이 분석은 입력크기 n과 입력값 x 모두에 종속되며 단위연산 수행 횟수가 최소인 경우 선택한다.
'Algorithms > Eff, Anal, and Order' 카테고리의 다른 글
| Order(차수) (0) | 2011.01.13 |
|---|---|
| Algorithms(알고리즘) (0) | 2011.01.07 |