기록 / 연습 / 단편

단위연산(basic operation): 알고리즘 내의 어떤 명령문이나 명령문 군을 선정하여, 알고리즘이 수행한 총 작업의 양을 이 명령문이나 명령문 군을 수행한 횟수에 대략적으로 비례하도록한다. 이 명령문 또는 명령문 군을 단위연산이라 한다.

시간복잡도 분석(time complexity analysis): 입력크기의 값에 대해서 단위연산을 몇 번 수행하는지를 구하는 것

입력 값에 상관 없이 입력크기에 따라 시간복잡도가 달라지는 경우

모든 경우 시간복잡도(every-case time complexity, T(n))

입력 값과 입력크기에 따라 시간복잡도가 달라지는 경우

최악의 경우 시간복잡도(worst-case time complexity, W(n)): 단위연산이 수행되는 최대 횟수 고려

평균의 경우 시간복잡도(average-case time complexity, A(n)): 알고리즘이 수행할 단위연산의 평균 횟수 고려, 입력 값에 대한 각각의 확률을 부여해야 함

최선의 경우 시간복잡도(best-case time complexity, B(n): 알고리즘이 수행할 단위연산의 최소 횟수 고려

* 모든 경우 시간복잡도를 구할 수 없는 알고리즘에 대하여, 최선의 경우 분석보다는 최악의 경우나 평균의 경우 분석을 훨씬 더 자주 실시함

큰 O(big O)

주어진 복잡도 함수 f(n)에 대해서, O(f(n))은 n ≥ N을 만족하는 모든 n에 대해 다음 부등식이 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

만약 g(n) ∈ O(f(n))이면, "g(n)은 f(n)의 큰 O이다"라고 한다.

예) 

위의 경우 n ≥ 10에 대해서는 다음과 같이 된다.

따라서 큰 O의 정의에서 c = 2와 N = 10을 취할 수 있으므로 다음과 같이 결론 지을 수 있다.

큰 O는 함수의 점근적인 상한(asymptotic upper bound)을 준다.

오메가(omega)

주어진 복잡도 함수 f(n)에 대해서, Ω(f(n))은 n ≥ N을 만족하는 모든 n에 대해 다음 부등식이 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

만약 g(n) ∈ Ω(f(n))이면, "g(n)은 f(n)의 오메가이다"라고 한다.

예) 

위의 경우 n ≥ 0에 대해서는 다음과 같이 된다.

따라서 오메가의 정의에서 c = 1과 N = 0을 취할 수 있으므로 다음과 같이 결론 지을 수 있다.

오메가는 함수의 점근적인 하한(asymptotic lower bound)를 나타낸다.

차수(order)

주어진 복잡도 함수 f(n)에 대해서, 다음과 같이 정의한다.

Θ(f(n))는 n ≥ N을 만족하는 모든 n에 대해서 다음 부등식이 만족하는 양의 실수 c, d와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

만약 g(n) ∈ Θ(f(n))이면, "g(n)은 f(n)의 차수이다"라고 한다.

작은 o(small o)

주어진 복잡도 함수 f(n)에 대해서, o(f(n))은 모든 양의 실수 c에 대해 n ≥ N을 만족하는 모든 n에 대하여 다음 부등식을 만족하는 음이 아닌 정수 N이 존재하는 모든 복잡도 함수 g(n)의 집합이다.

만약 g(n) ∈ o(f(n))이면, "g(n)은 f(n)의 작은 o이다"라고 한다.

위의 정의는 모든 양의 실수 c에 대해서 그 범위가 성립해야 하므로 g(n)은 f(n)같은 함수보다는 궁극적으로 훨씬 좋다.

내용 출처

Foundations of Algorithms Using C++ Pseudocode 3rd Edition 알고리즘; Richard Neapolitan, Kumarss Naimipour; 도경구 역; 사이텍미디어

그림 출처

GeeksforGeeks, http://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/