1. 차수(Order)
- 어떤 1차 시간(linear-time) 알고리즘이 어떤 2차 시간(quadratic-time) 알고리즘 보다 더 효율적이다.
- 일반적으로 고차항이 시간 복잡도를 지배한다.
ex)
주1 : 0.01n^2 >= 100n ( n >= 10,000)
주2 : n = 1,000,000 일때 0.01n^2과 0.01n^2+100n+10,000의 값은 거의 같다고 볼 수 있다.
> 0.01n^2+100n+10,000에서 n^2의 항이 식을 지배함.
2. 큰(Big) O 표기법
- 정의
주어진 복잡도 함수 f(n)에 대해서 O(f(n))은 n>=N인 모든 정수 n에 대해서 g(n) <= c*f(n)을 만적시키는
실수 상수 c (c>0)와 음이 아닌 정수 N이 존재하는 g(n)함수들의 집합이다.
- g(n) ∈ O(f(n))이라면 우리는 g(n)은 f(n)의
큰 (Big) O라고 말한다.
- 어떤 함수 g(n)이 O(n^2)에 속한다는 말은
> 함수 g(n)은 어떤 임의의 N값보다 큰 값에 대해서 는 어떤 2차 함수 cn^2보다 작은 값을 가지게 된다 는 것을 의미한다.
> 함수 g(n)은 어떤 2차 함수 cn^2보다는 궁극적으 로 더 좋다고 말할 수 있다.
- 어떤 함수 g(n)이 O(f(n))에 속한다는 말은
> 입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 늦어도 f(n)이 된다. ( f(n)은 상한이다. )
> 이 알고리즘의 수행시간은 f(n)보다 절대로 더 느릴 수 없다는 의미이다.
ex1) n^2 + 10n ∈ O(n^2) 성립하는가?
n >= 1인 모든 n에 대해서 n^2 + 10n <= n^2 + 10 n^2 = 11n^2
> c = 11 / N = 1 // c와 N값이 존재하므로 성립한다.
ex2) n^3 ∈ O(n^2) 성립하는가?
n >= N인 모든 n에 대해서 n^3 <= cn^2인 C와 N은 존재하지 않는다. 즉, 양변을 n^2으로 나누면, n<=c가
된다. c를 아무리 크게 잡더라도 그보다 더 큰 n이 존재한다. // 성립X
3. Ω표기법
- 정의
주어진 복잡도 함수 f(n)에 대해서 Ω(f(n))은 n >= N인 모든 정수 n에 대해서 g(n) >= cf(n)을 만족 시키는 실수 상수 c (c>0)와 음이 아닌 정수 N인 존재하는 g(n)함수들의 집합이다.
- g(n) ∈ Ω(f(n))이라면 g(n)은 f(n)의 Ω라고 말한다.
- 어떤함수 g(n)이 Ω(n^2)에 속한다는 말은
> 함수 g(n)은 어떤 임의의 N값보다 큰 값에 대해서
어떤 2차 함수 cn^2보다 큰 값을 가지게 된다는 것 을 의미한다.
> 함수 g(n)은 어떤 2차 함수 cn^2보다는 궁극적으 로 더 나쁘다고 말할 수 있다.
- 어떤 알고리즘의 시간 복잡도가 Ω(f(n))이라면
> 입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 빨라도 f(n) 밖에 안된다.(f(n)이 하한이다)
> 다시 말하면, 이 알고리즘의 수행시간은 f(n)보다 절대로 더 빠를 수 없다는 의미이다.
ex3) T(n) = n(n-1)/2 ∈ Ω(n^2) ?
n >= 2인 모든 n에 대해서 n-1 >= n/2
따라서, n>=2인 모든 n에 대해서 n(n-1)/2 >= n/2*n/2 = 1/4n^2
C = 1/4, N =2 // C와 N의 값을 가지기 때문에 이는 성립한다.
ex4) n ∈ Ω(n^2)
모순유도에 의한 증명(Proof by contradiction)에 의해 증명한다.
n ∈ Ω(n^2)이라고 가정하자. 그러면 n >= N인 모든 정수 n에 대해서 n >= cn^2을 만족시키는 실수상수
c>0와 음이 아닌 정수 N이 존재해야한다. 그러나 위 부등식을 cn으로 나누면
1/c >= n 따라서 이 부등식은 절대로 성립할 수 없다. 따라서 위의 가정은 잘못 되었다.
4. ⊝ 표기법
- 정의
주어진 복잡도 함수 f(n)에 대해서 ⊝(f(n)) = O(f(n)) ∩ Ω(f(n)).
즉, ⊝(f(n))은 n>=N인 모든 n에 대해서 cf(n) <= g(n) <= df(n)을 만족시키는 실수 c,d(c/d > 0 )와 음이 아닌
정수 N이 존재하는 g(n)함수들의 집합이다.
- g(n) ∈ ⊝(f(n)) 이라면 우리는 g(n)은 f(n)의 차수 (Order)라고 말한다.
ex5) T(n) = n(n-1)/2 ∈ ⊝(n^2) 이 성립하는가?
n >= 0 인 모든 n에 대해서 n(n-1)/2 >= n*n/2 = n^2/2
따라서, C = 1/2, N =0 >> T(n) ∈ O(n^2)
예제 3에 의해 T(n) ∈ Ω(n^2) 이 성립
따라서, T(n) ∈ ⊝(n^2) 이 성립한다.
- 어떤 1차 시간(linear-time) 알고리즘이 어떤 2차 시간(quadratic-time) 알고리즘 보다 더 효율적이다.
- 일반적으로 고차항이 시간 복잡도를 지배한다.
ex)
주1 : 0.01n^2 >= 100n ( n >= 10,000)
주2 : n = 1,000,000 일때 0.01n^2과 0.01n^2+100n+10,000의 값은 거의 같다고 볼 수 있다.
> 0.01n^2+100n+10,000에서 n^2의 항이 식을 지배함.
2. 큰(Big) O 표기법
- 정의
주어진 복잡도 함수 f(n)에 대해서 O(f(n))은 n>=N인 모든 정수 n에 대해서 g(n) <= c*f(n)을 만적시키는
실수 상수 c (c>0)와 음이 아닌 정수 N이 존재하는 g(n)함수들의 집합이다.
- g(n) ∈ O(f(n))이라면 우리는 g(n)은 f(n)의
큰 (Big) O라고 말한다.
- 어떤 함수 g(n)이 O(n^2)에 속한다는 말은
> 함수 g(n)은 어떤 임의의 N값보다 큰 값에 대해서 는 어떤 2차 함수 cn^2보다 작은 값을 가지게 된다 는 것을 의미한다.
> 함수 g(n)은 어떤 2차 함수 cn^2보다는 궁극적으 로 더 좋다고 말할 수 있다.
- 어떤 함수 g(n)이 O(f(n))에 속한다는 말은
> 입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 늦어도 f(n)이 된다. ( f(n)은 상한이다. )
> 이 알고리즘의 수행시간은 f(n)보다 절대로 더 느릴 수 없다는 의미이다.
ex1) n^2 + 10n ∈ O(n^2) 성립하는가?
n >= 1인 모든 n에 대해서 n^2 + 10n <= n^2 + 10 n^2 = 11n^2
> c = 11 / N = 1 // c와 N값이 존재하므로 성립한다.
ex2) n^3 ∈ O(n^2) 성립하는가?
n >= N인 모든 n에 대해서 n^3 <= cn^2인 C와 N은 존재하지 않는다. 즉, 양변을 n^2으로 나누면, n<=c가
된다. c를 아무리 크게 잡더라도 그보다 더 큰 n이 존재한다. // 성립X
3. Ω표기법
- 정의
주어진 복잡도 함수 f(n)에 대해서 Ω(f(n))은 n >= N인 모든 정수 n에 대해서 g(n) >= cf(n)을 만족 시키는 실수 상수 c (c>0)와 음이 아닌 정수 N인 존재하는 g(n)함수들의 집합이다.
- g(n) ∈ Ω(f(n))이라면 g(n)은 f(n)의 Ω라고 말한다.
- 어떤함수 g(n)이 Ω(n^2)에 속한다는 말은
> 함수 g(n)은 어떤 임의의 N값보다 큰 값에 대해서
어떤 2차 함수 cn^2보다 큰 값을 가지게 된다는 것 을 의미한다.
> 함수 g(n)은 어떤 2차 함수 cn^2보다는 궁극적으 로 더 나쁘다고 말할 수 있다.
- 어떤 알고리즘의 시간 복잡도가 Ω(f(n))이라면
> 입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 빨라도 f(n) 밖에 안된다.(f(n)이 하한이다)
> 다시 말하면, 이 알고리즘의 수행시간은 f(n)보다 절대로 더 빠를 수 없다는 의미이다.
ex3) T(n) = n(n-1)/2 ∈ Ω(n^2) ?
n >= 2인 모든 n에 대해서 n-1 >= n/2
따라서, n>=2인 모든 n에 대해서 n(n-1)/2 >= n/2*n/2 = 1/4n^2
C = 1/4, N =2 // C와 N의 값을 가지기 때문에 이는 성립한다.
ex4) n ∈ Ω(n^2)
모순유도에 의한 증명(Proof by contradiction)에 의해 증명한다.
n ∈ Ω(n^2)이라고 가정하자. 그러면 n >= N인 모든 정수 n에 대해서 n >= cn^2을 만족시키는 실수상수
c>0와 음이 아닌 정수 N이 존재해야한다. 그러나 위 부등식을 cn으로 나누면
1/c >= n 따라서 이 부등식은 절대로 성립할 수 없다. 따라서 위의 가정은 잘못 되었다.
4. ⊝ 표기법
- 정의
주어진 복잡도 함수 f(n)에 대해서 ⊝(f(n)) = O(f(n)) ∩ Ω(f(n)).
즉, ⊝(f(n))은 n>=N인 모든 n에 대해서 cf(n) <= g(n) <= df(n)을 만족시키는 실수 c,d(c/d > 0 )와 음이 아닌
정수 N이 존재하는 g(n)함수들의 집합이다.
- g(n) ∈ ⊝(f(n)) 이라면 우리는 g(n)은 f(n)의 차수 (Order)라고 말한다.
ex5) T(n) = n(n-1)/2 ∈ ⊝(n^2) 이 성립하는가?
n >= 0 인 모든 n에 대해서 n(n-1)/2 >= n*n/2 = n^2/2
따라서, C = 1/2, N =0 >> T(n) ∈ O(n^2)
예제 3에 의해 T(n) ∈ Ω(n^2) 이 성립
따라서, T(n) ∈ ⊝(n^2) 이 성립한다.