The Big Oh Notation - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:25:15Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:25 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[알고리즘 설계와 분석#알고리즘 분석\|알고리즘 설계와 분석]]		상위 문서: [[알고리즘 설계와 분석#알고리즘 분석\|알고리즘 설계와 분석]]

Pinkgo: /* Dominance Relations */

2025-09-06T00:38:54Z

Dominance Relations

← 이전 판		2025년 9월 6일 (토) 00:38 판
60번째 줄:		60번째 줄:
	아래는 각 함수에 대한 지배 관계를 나타낸 것이다:		아래는 각 함수에 대한 지배 관계를 나타낸 것이다:
	<math>n! \gg 2^n \gg n^3 \gg n^2 \gg n\cdot log(n) \gg n \gg log(n) \gg 1</math>		<math>n! \gg 2^n \gg n^3 \gg n^2 \gg n\cdot log(n) \gg n \gg log(n) \gg 1</math>
			이때 주의할 점은 로그에서의 밑은 중요하지 않다는 것이다. 그 이유는 아래와 같은 수학 공식이 성립하기 때문이다:
			<math>log_ba = \frac{log_cb}{log_ca}</math>
			즉, 로그의 밑을 바꾸는 것은 단순히 계수에 영향을 주기 때문에 무시할 수 있다.

	==각주==		==각주==

Pinkgo: /* Growth Rates and Dominance Relations */

2025-09-06T00:19:34Z

Growth Rates and Dominance Relations

← 이전 판		2025년 9월 6일 (토) 00:19 판
45번째 줄:		45번째 줄:

	==Growth Rates and Dominance Relations==		==Growth Rates and Dominance Relations==
			[[파일:Figure 2. Asymptotic Dominance in Action.png\|섬네일\|400x400픽셀\|Figure 2. Asymptotic Dominance in Action]]
	빅 오 표기를 사용하면 분석할 시간 복잡도 함수들의 계수들을 버릴 수 있다. 따라서 <math>f(n) = 0.001n^2, g(n) = 1000n^2</math>는 동일하게 취급된다. 이는 다소 거칠게 보일 수 있지만, 이는 상당히 유용하다. 그 이유는 figure 2에 나타나 있는 도표를 통해서 해당 알고리즘의 빅 오 표기를 통해서 해당 알고리즘의 실용성을 판단할 수 있기 때문이다. 해당 표에서는 아래와 같은 결론을 도출할 수 있다.		빅 오 표기를 사용하면 분석할 시간 복잡도 함수들의 계수들을 버릴 수 있다. 따라서 <math>f(n) = 0.001n^2, g(n) = 1000n^2</math>는 동일하게 취급된다. 이는 다소 거칠게 보일 수 있지만, 이는 상당히 유용하다. 그 이유는 figure 2에 나타나 있는 도표를 통해서 해당 알고리즘의 빅 오 표기를 통해서 해당 알고리즘의 실용성을 판단할 수 있기 때문이다. 해당 표에서는 아래와 같은 결론을 도출할 수 있다.
	* n = 10일 때에는 거의 모든 알고리즘이 동일한 시간을 소요한다.		* n = 10일 때에는 거의 모든 알고리즘이 동일한 시간을 소요한다.

Pinkgo: /* Reasoning about Efficiency */

2025-09-06T00:17:51Z

Reasoning about Efficiency

@@ 43번째 줄: / 43번째 줄: @@
 ==Reasoning about Efficiency==
 알고리즘의 실행 시간에 대한 추론은 보통 쉽다. 이에 대한 예시는 [[Sorting Problem]]에 대한 문서를 참조하면 된다.
 ==각주==

2025년 9월 5일 (금) 22:49에 Pinkgo님의 편집

2025-09-05T22:49:05Z

← 이전 판		2025년 9월 5일 (금) 22:49 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
			상위 문서: [[알고리즘 설계와 분석#알고리즘 분석\|알고리즘 설계와 분석]]

	==개요==		==개요==

2025년 9월 5일 (금) 22:28에 Pinkgo님의 편집

2025-09-05T22:28:09Z

← 이전 판		2025년 9월 5일 (금) 22:28 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]


	==개요==		==개요==

2025년 9월 5일 (금) 22:27에 Pinkgo님의 편집

2025-09-05T22:27:55Z

← 이전 판		2025년 9월 5일 (금) 22:27 판
40번째 줄:		40번째 줄:
	<math>\Omega(f(n)) \cdot \Omega(g(n)) \rightarrow \Omega(f(n) \cdot g(n))</math>		<math>\Omega(f(n)) \cdot \Omega(g(n)) \rightarrow \Omega(f(n) \cdot g(n))</math>
	<math>\Theta(f(n)) \cdot \Theta(g(n)) \rightarrow \Theta(f(n) \cdot g(n))</math>		<math>\Theta(f(n)) \cdot \Theta(g(n)) \rightarrow \Theta(f(n) \cdot g(n))</math>

			==Reasoning about Efficiency==
			알고리즘의 실행 시간에 대한 추론은 보통 쉽다. 이에 대한 예시는 [[Sorting Problem]]에 대한 문서를 참조하면 된다.

	==각주==		==각주==

Pinkgo: /* Big Oh Addition/Subtraction */

2025-09-05T22:23:50Z

Big Oh Addition/Subtraction

← 이전 판		2025년 9월 5일 (금) 22:23 판
19번째 줄:		19번째 줄:
	이러한 정의들은 figure 1에 잘 제시되어 있다. 이들 정의 각각은 어떤 상수 n<sub>0</sub>가 존재하여 그 이후에는 조건이 만족된다는 것을 보여준다.		이러한 정의들은 figure 1에 잘 제시되어 있다. 이들 정의 각각은 어떤 상수 n<sub>0</sub>가 존재하여 그 이후에는 조건이 만족된다는 것을 보여준다.

	==Big Oh Addition/Subtraction==		==Working with the Big Oh==
			일반적인 대수 계산을 빅 오 표기에 적용하는 것은 중요하면서도 조금 모호하다. 이는 대부분의 대수 계산에 대한 상식이 유지되면서도 꼭 모두 적용된다고는 말할 수 없기 때문이다.

			===Big Oh Addition/Subtraction===
	어떠한 차수가 같은 함수 <math>f(n), g(n)</math>에 대해 <math>f(n) = O(n^2), g(n) = O(n^2)</math>를 가정해 보자. 이때 함수 <math>g'(n) = f(n) + g(n)</math>에 대한 빅 오 표기는 아래와 같이 계산할 수 있다.		어떠한 차수가 같은 함수 <math>f(n), g(n)</math>에 대해 <math>f(n) = O(n^2), g(n) = O(n^2)</math>를 가정해 보자. 이때 함수 <math>g'(n) = f(n) + g(n)</math>에 대한 빅 오 표기는 아래와 같이 계산할 수 있다.
	<math>f(n) \le c_1 \cdot n^2, g(n) \le c_2 \cdot n^2</math>이라 하면		<math>f(n) \le c_1 \cdot n^2, g(n) \le c_2 \cdot n^2</math>이라 하면
26번째 줄:		29번째 줄:
	<math>f(n) = n^2, g(n) = n^2</math>이라면 , <math>f(n) - g(n) = 0</math>		<math>f(n) = n^2, g(n) = n^2</math>이라면 , <math>f(n) - g(n) = 0</math>
	<math>f(n) = 2 \cdot n^2, g(n) = n^2</math>이라면, <math>f(n) - g(n) = n^2</math>		<math>f(n) = 2 \cdot n^2, g(n) = n^2</math>이라면, <math>f(n) - g(n) = n^2</math>
	따라서 어떤 차수가 같은 함수 <math>f(n), g(n)</math>에 대해 뺼셈을 진행한다면, 일반적으로 <math>O(n^2)</math>라고 말할 수 있을 뿐이며, 해당 차수가 보존되는 지에 대해서는 말할 수 없다.		따라서 어떤 차수가 같은 함수 <math>f(n), g(n)</math>에 대해 뺼셈을 진행한다면, 일반적으로 <math>O(n^2)</math>라고 말할 수 있을 뿐이며, 해당 차수가 보존되는 지에 대해서는 말할 수 없다.

			===Multiplying Functions===
			곱셈은 반복된 덧셈과 같이 취급할 수 있다. 따라서, <math>c > 0</math>를 만족하는 상수 c에 대해 아래와 같이 계산된다.
			<math>O(c \cdot g(n)) \rightarrow O(g(n))</math>
			<math>\Omega(c \cdot g(n)) \rightarrow \Omega(g(n))</math>
			<math>\Theta(c \cdot g(n)) \rightarrow \Theta(g(n))</math>
			하지만 증가함수인 두 함수를 서로 곱하는 경우에는, 두 함수가 모두 결과에 준다. 이는 아래와 같이 나타낼 수 있다.
			<math>O(f(n)) \cdot O(g(n)) \rightarrow O(f(n) \cdot g(n))</math>
			<math>\Omega(f(n)) \cdot \Omega(g(n)) \rightarrow \Omega(f(n) \cdot g(n))</math>
			<math>\Theta(f(n)) \cdot \Theta(g(n)) \rightarrow \Theta(f(n) \cdot g(n))</math>

	==각주==		==각주==

2025년 9월 5일 (금) 22:07에 Pinkgo님의 편집

2025-09-05T22:07:00Z

← 이전 판		2025년 9월 5일 (금) 22:07 판
9번째 줄:		9번째 줄:

	==내용==		==내용==
			[[파일:Figure 1. Big Oh, Omega, Theta.png\|섬네일\|Figure 1. Big Oh, Omega, Theta]]
	“빅 오(Big Oh)” 표기는 시간 복잡도 함수를 상한/하한으로 나타내어 이를 단순화 하는 방식이다. 함수 <math>f(n) = 2n</math>과 <math>g(n) = n</math>은 빅 오 분석에서 동일하다. 빅 오 표기에는 아래와 같은 세 가지 정의가 존재한다.		“빅 오(Big Oh)” 표기는 시간 복잡도 함수를 상한/하한으로 나타내어 이를 단순화 하는 방식이다. 함수 <math>f(n) = 2n</math>과 <math>g(n) = n</math>은 빅 오 분석에서 동일하다. 빅 오 표기에는 아래와 같은 세 가지 정의가 존재한다.
	* <math>f(n) = O(g(n))</math>는 <math>c\cdot g(n)</math>가 <math>f(n)</math>에 대한 상한임을 의미한다.		* <math>f(n) = O(g(n))</math>는 <math>c\cdot g(n)</math>가 <math>f(n)</math>에 대한 상한임을 의미한다.

2025년 9월 5일 (금) 22:05에 Pinkgo님의 편집

2025-09-05T22:05:31Z

← 이전 판		2025년 9월 5일 (금) 22:05 판
6번째 줄:		6번째 줄:
	주어진 어떤 알고리즘에 대한 시간 복잡도는 가능한 문제 인스턴스 크기에 대한 함수들이며, 이들을 정밀하게 다루는 것은 매우 어렵다. 따라서 이들을 단순화하여 분석하는 것이 매우 좋은 방식 중 하나이다. 예를 들어, <math>T(n) = 12754n^2 + 4353n + 834log_2^n + 13546</math>와 같은 시간 복잡도 함수는 정밀하게 분석하기란 매우 어렵지만, 시간 복잡도가 n에 대해 2차적으로 증가한다는 관찰이 틀렸다고 볼 수는 없다.		주어진 어떤 알고리즘에 대한 시간 복잡도는 가능한 문제 인스턴스 크기에 대한 함수들이며, 이들을 정밀하게 다루는 것은 매우 어렵다. 따라서 이들을 단순화하여 분석하는 것이 매우 좋은 방식 중 하나이다. 예를 들어, <math>T(n) = 12754n^2 + 4353n + 834log_2^n + 13546</math>와 같은 시간 복잡도 함수는 정밀하게 분석하기란 매우 어렵지만, 시간 복잡도가 n에 대해 2차적으로 증가한다는 관찰이 틀렸다고 볼 수는 없다.

	“빅 오(Big Oh)” 표기는 시간 복잡도 함수를 상한/하한으로 나타내어 이를 단순화 하는 방식이다~~. 빅 오 표기는 곱셈 상수들 간의 차이를 무시한다~~. 함수 <math>f(n) = 2n</math>과 <math>g(n) = n</math>은 빅 오 분석에서 동일하다. 빅 오 표기에는 아래와 같은 세 가지 정의가 존재한다.		해당 문서에서는 이러한 특성을 이용한 “빅 오(Big Oh)” 표기에 대해 알아본다.

			==내용==
			“빅 오(Big Oh)” 표기는 시간 복잡도 함수를 상한/하한으로 나타내어 이를 단순화 하는 방식이다. 함수 <math>f(n) = 2n</math>과 <math>g(n) = n</math>은 빅 오 분석에서 동일하다. 빅 오 표기에는 아래와 같은 세 가지 정의가 존재한다.
	* <math>f(n) = O(g(n))</math>는 <math>c\cdot g(n)</math>가 <math>f(n)</math>에 대한 상한임을 의미한다.		* <math>f(n) = O(g(n))</math>는 <math>c\cdot g(n)</math>가 <math>f(n)</math>에 대한 상한임을 의미한다.
	** 따라서 어떤 상수 c가 존재하여 충분히 큰 모든 n에 대하여 <math>f(n) \le c \cdot g(n)</math>가 성립한다.		** 따라서 어떤 상수 c가 존재하여 충분히 큰 모든 n에 대하여 <math>f(n) \le c \cdot g(n)</math>가 성립한다.
15번째 줄:		18번째 줄:
	이러한 정의들은 figure 1에 잘 제시되어 있다. 이들 정의 각각은 어떤 상수 n<sub>0</sub>가 존재하여 그 이후에는 조건이 만족된다는 것을 보여준다.		이러한 정의들은 figure 1에 잘 제시되어 있다. 이들 정의 각각은 어떤 상수 n<sub>0</sub>가 존재하여 그 이후에는 조건이 만족된다는 것을 보여준다.

			==Big Oh Addition/Subtraction==
			어떠한 차수가 같은 함수 <math>f(n), g(n)</math>에 대해 <math>f(n) = O(n^2), g(n) = O(n^2)</math>를 가정해 보자. 이때 함수 <math>g'(n) = f(n) + g(n)</math>에 대한 빅 오 표기는 아래와 같이 계산할 수 있다.
			<math>f(n) \le c_1 \cdot n^2, g(n) \le c_2 \cdot n^2</math>이라 하면
			<math>g'(n) = f(n) + g(n) \le (c_1 + c_2)n^2, \therefore g'(n) = O(n^2)</math>
			즉, 같은 차수의 함수끼리 더해도 결국 그 차수는 변하지 않는다. 하지만 빅 오 표기에서의 뺄셈은 최대 차수의 계수에 따라 그 결과가 달라지기 때문에, 모호하게 작동한다. 예를 들어 함수 <math>g''(n) = f(n) - \|g(n)\|</math>에 대해:
			<math>f(n) = n^2, g(n) = n^2</math>이라면 , <math>f(n) - g(n) = 0</math>
			<math>f(n) = 2 \cdot n^2, g(n) = n^2</math>이라면, <math>f(n) - g(n) = n^2</math>
			따라서 어떤 차수가 같은 함수 <math>f(n), g(n)</math>에 대해 뺼셈을 진행한다면, 일반적으로 <math>O(n^2)</math>라고 말할 수 있을 뿐이며, 해당 차수가 보존되는 지에 대해서는 말할 수 없다.

	==각주==		==각주==