빈 알고리즘의 시간 복잡도는 O (0)입니까?

빈 알고리즘의 시간 복잡도는 O (0)입니까?

---

따라서 다음 프로그램이 주어집니다.

---

이 프로그램의 시간 복잡도는 O (0)입니까? 즉, 0 O (0)입니까?

나는 되거 것 별도의 질문이 답 생각 이 질문에 .

편집 : 여기에 좋은 답변이 많이 있습니다! 우리 모두는 0이 O (1)라는 데 동의합니다. 문제는 0 O (0)입니다.

---

에서 위키 백과 :

big O 표기법으로 함수에 대한 설명은 일반적으로 함수의 성장률에 대한 상한 만 제공합니다.

이 설명에서 빈 알고리즘은 실행 시간이 0이 필요하므로 상한 성능은 O (0)입니다. 이것은 또한 더 큰 상한이되는 O (1)임을 의미합니다.

편집 :

CLR에서보다 공식적으로 (1ed, pg 26) :

주어진 함수 g ( n )에 대해 우리는 O ( g ( n )) 함수 집합을 나타냅니다.

O ( g ( N ))은 = { F ( N ) : 양의 정수가 존재 C 및 N ₀ 이되도록 0 ≤ F (N) ≤ CG ( N 모두) N ≥ n은 ₀ }

따라서 입력에 관계없이 0 시간에 실행되는 빈 알고리즘의 점근 적 시간 성능은 O (0) 의 구성원입니다 .

편집 2 :

우리 모두는 0이 O (1)라는 데 동의합니다. 문제는 0 O (0)입니다.

정의에 따라 예라고 말합니다.

또한 많은 답변이 나타내는 것보다 질문에 약간 더 의미가 있다고 생각합니다. 그 자체로 빈 알고리즘은 아마도 의미가 없을 것입니다. 그러나 사소하지 않은 알고리즘이 지정 될 때마다 빈 알고리즘은 지정된 알고리즘의 연속 단계와 알고리즘 단계 전후에있는 것으로 간주 할 수 있습니다. "아무것도"가 알고리즘의 점근 적 시간 성능에 영향을 미치지 않는다는 것을 아는 것이 좋습니다.

편집 3 :

Adam Crume 은 다음과 같은 주장을합니다 .

모든 함수 f ( x )에 대해 f ( x )는 O ( f ( x ))에 있습니다.

증명 : S 를 R 의 부분 집합으로 하고 T 를 R ^* (음이 아닌 실수) 의 부분 집합으로 하고 f ( x ) : S- > T 및 c ≥ 1이면 0 ≤ f ( x ) ≤ f ( x ) 모든 x∈ S에 대해 0 ≤ f ( x ) ≤ cf ( x )가됩니다 . 따라서 f ( x ) ∈ O ( f ( x )).

특히 f ( x ) = 0이면 f ( x ) ∈ O (0)입니다.

---

입력에 관계없이 실행하는 데 동일한 시간이 걸리므로 정의에 따라 O (1)입니다.

---

시간은 상수이고 시간은 어떤 계수와 1의 곱에 의해 제한되기 때문에 복잡도는 O (1)이라고 여러 대답은 말합니다. 음, 시간이 상수이고 그렇게 제한되어 있다는 것은 사실입니다. 그렇다고 가장 좋은 답이 O (1)라는 뜻은 아닙니다.

선형 시간으로 실행되는 알고리즘을 고려하십시오. 일반적으로 O (n)로 지정되어 있지만 악마의 옹호자 역할을합시다. 시간은 어떤 계수와 n ^ 2의 곱에 의해 제한됩니다. O (n ^ 2)를 복잡성이 충분히 작은 모든 알고리즘의 집합 인 집합으로 간주하면 선형 알고리즘이 해당 집합에 있습니다. 그러나 이것이 가장 좋은 답이 O (n ^ 2)라는 의미는 아닙니다.

빈 알고리즘은 O (n ^ 2) 및 O (n) 및 O (1) 및 O (0)에 있습니다. 나는 O (0)에 투표합니다.

---

빈 알고리즘에 대한 매우 간단한 인수가 O (0)입니다. 모든 함수 f (x)의 경우 f (x)는 O (f (x))에 있습니다. 간단히 f (x) = 0으로두면 0 (빈 알고리즘의 실행 시간)이 O (0)에 있습니다.

참고로, 사람들이 f (x) = O (g (x))라고 쓸 때, 그것이 f (x) ∈ O (g (x)) 여야 할 때가 싫어요.

---

Big O는 점근 표기법입니다. big O를 사용하려면 함수 가 필요합니다. 즉, n이 사용되지 않더라도 표현식을 n으로 매개 변수화해야합니다. 숫자 5가 O (n)이라고 말하는 것은 의미가 없으며 O (n) 인 상수 함수 f (n) = 5입니다.

따라서 큰 O 측면에서 시간 복잡도를 분석하려면 n의 함수가 필요합니다. 귀하의 알고리즘은 항상 0 단계를 수행하지만 점근 적 동작에 대해 말하는 가변 매개 변수가 없으면 의미가 없습니다. 알고리즘이 n으로 매개 변수화되었다고 가정합니다. 지금 만 점근 표기법을 사용할 수 있습니다. n (또는 O (1)에 숨겨진 변수)을 지정하지 않으면 O (n ² ) 또는 O (1) 이라고 말하는 것은 의미 가 없습니다!

단계 수를 결정하자마자 큰 O의 정의 문제입니다. 함수 f (n) = 0은 O (0)입니다.

이것은 낮은 수준의 질문이므로 계산 모델에 따라 다릅니다. "이상적인"가정 하에서는 아무것도하지 않을 수 있습니다. 그러나 파이썬에서, 당신은 말할 수 없습니다 def f(x):만, def f(x): pass. 모든 명령어 pass(NOP) 에도 시간이 걸린다고 가정하면 일부 상수 c에 대해 복잡도는 f (n) = c이며 O (0)이 아니라 O (1) c != 0이라고 만 말할 수 f없습니다.

Big O 자체가 알고리즘과 관련이 없다는 점은 주목할 가치가 있습니다. 예를 들어, Taylor 확장을 논의 할 때 sin x = x + O (x ³ ) 라고 말할 수 있습니다 . 또한 O (1)은 상수가 아니라 상수로 묶인 것을 의미합니다.

---

지금까지의 모든 대답은 옳고 그른 대답이있는 것처럼 질문을 다룹니다. 그러나 없습니다. 문제는 정의의 문제입니다. 일반적으로 복잡성 이론에서 시간 비용은 정수입니다. 즉시 종료되는 빈 알고리즘은 0 시간 단계 또는 1 시간 단계를 취한다고 자유롭게 말할 수 있습니다. 시간 복잡성은 추상적 인 정의이기 때문에 추상적 인 질문입니다. 현실 세계에서는 시간 단계도없고 물리적 인 시간이 계속됩니다. 하나의 CPU에 클럭 사이클이있는 것이 사실 일 수 있지만 병렬 컴퓨터는 쉽게 비동기 클럭을 가질 수 있으며 어떤 경우에도 클럭 사이클은 매우 작습니다.

즉, 정지 작업은 0 시간 단계가 걸리는 것보다 1 시간 단계가 걸린다고 말하는 것이 더 합리적이라고 말할 수 있습니다. 더 현실적으로 보입니다. 많은 상황에서 초기화의 오버 헤드가 일반적으로 하나의 산술 또는 논리 연산을 실행하는 것보다 훨씬 크기 때문에 매우 보수적입니다. 빈 알고리즘에 0 시간 단계를 제공하는 것은 예를 들어 함수가 아무 작업도 수행하지 않음을 알고있는 최적화 컴파일러에 의해 삭제 된 함수 호출을 모델링하는 데만 합리적입니다.

---

O (1)이어야합니다. 계수는 항상 1입니다.

중히 여기다:

5n처럼 커지면 O (5n)이 아니라 O (n) [즉, O (1n)]이라고 말합니다.

7n ^ 2처럼 커지면 O (7n ^ 2)라고하지 않고 O (n ^ 2) [즉, O (1n ^ 2)]라고 말합니다.

마찬가지로 O (다른 상수)가 아니라 O (1)이라고 말해야합니다.

---

There is no such thing as O(0). Even an oracle machine or a hypercomputer require the time for one operation, i.e. solve(the_goldbach_conjecture), ergo:

All machines, theoretical or real, finite or infinite produce algorithms with a minimum time complexity of O(1).

But then again, this code right here is O(0):

// Hello world!

:)

---

I would say it's O(1) by definition, but O(0) if you want to get technical about it: since O(k₁g(n)) is equivalent to O(k₂g(n)) for any constants k₁ and k₂, it follows that O(1 * 1) is equivalent to O(0 * 1), and therefore O(0) is equivalent to O(1).

However, the empty algorithm is not like, for example, the identity function, whose definition is something like "return your input". The empty algorithm is more like an empty statement, or whatever happens between two statements. Its definition is "do absolutely nothing with your input", presumably without even the implied overhead of simply having input.

Consequently, the complexity of the empty algorithm is unique in that O(0) has a complexity of zero times whatever function strikes your fancy, or simply zero. It follows that since the whole business is so wacky, and since O(0) doesn't already mean something useful, and since it's slightly ridiculous to even discuss such things, a reasonable special case for O(0) is something like this:

The complexity of the empty algorithm is O(0) in time and space. An algorithm with time complexity O(0) is equivalent to the empty algorithm.

So there you go.

---

Given the formal definition of Big O:

Let f(x) and g(x) be two functions defined over the set of real numbers. Then, we write:

f(x) = O(g(x)) as x approaches infinity iff there exists a real M and a real x0 so that:

|f(x)| <= M * |g(x)| for every x > x0

As I see it, if we substitute g(x) = 0 (in order to have a program with complexity O(0)), we must have:

|f(x)| <= 0, for every x > x0 (the constraint of existence of a real M and x0 is practically lifted here)

which can only be true when f(x) = 0.

So I would say that not only the empty program is O(0), but it is the only one for which that holds. Intuitively, this should've been true since O(1) encompasses all algorithms that require a constant number of steps regardless of the size of its task, including 0. It's essentially useless to talk about O(0); it's already in O(1). I suspect it's purely out of simplicity of definition that we use O(1), where it could as well be O(c) or something similar.

---

0 = O(f) for all function f, since 0 <= |f|, so it is also O(0).

---

O(1) means the algorithm's time complexity is always constant.

Let's say we have this algorithm (in C):

void doSomething(int[] n)
{
  int x = n[0]; // This line is accessing an array position, so it is time consuming.
  int y = n[1]; // Same here.
  return x + y;
}

I am ignoring the fact that the array could have less than 2 positions, just to keep it simple.

If we count the 2 most expensive lines, we have a total time of 2.

2 = O(1), because:

2 <= c * 1, if c = 2, for every n > 1

If we have this code:

public void doNothing(){}

And we count it as having 0 expansive lines, there is no difference in saying it has O(0) O(1), or O(1000), because for every one of these functions, we can prove the same theorem.

Normally, if the algorithm takes a constant number of steps to complete, we say it has O(1) time complexity.

I guess this is just a convention, because you could use any constant number to represent the function inside the O().

---

No. It's O(c) by convention whenever you don't have dependence on input size, where c is any positive constant (typically 1 is used - O(1) = O(12.37)).

ReferenceURL : https://stackoverflow.com/questions/3209139/is-the-time-complexity-of-the-empty-algorithm-o0