O (n) 알고리즘이 계산 시간 측면에서 O (n ^ 2)를 초과 할 수 있습니까?

O (n) 알고리즘이 계산 시간 측면에서 O (n ^ 2)를 초과 할 수 있습니까?

---

두 가지 알고리즘이 있다고 가정합니다.

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

이것은 당연 O(n^2)합니다. 또한 다음이 있다고 가정합니다.

for (int i = 0; i < 100; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

이것은 O(n) + O(n) + O(n) + O(n) + ... O(n) + = O(n)

두 번째 알고리즘이 O(n)이지만 시간이 더 오래 걸리는 것 같습니다 . 누군가 이것을 확장 할 수 있습니까? 예를 들어 정렬 단계를 먼저 수행하거나 이와 유사한 작업을 수행하는 알고리즘을 자주보고 전체 복잡성을 결정할 때 알고리즘을 경계하는 가장 복잡한 요소를 자주 볼 수 있기 때문입니다.

---

점근 적 복잡도 (big-O와 big-Theta가 모두 나타내는 것)는 관련된 상수 요소를 완전히 무시합니다. 입력 크기가 커짐에 따라 실행 시간이 어떻게 변경되는지 표시하기위한 것일뿐입니다.

그것이 것을 확실히 가능 그래서 Θ(n)알고리즘이보다 오래 걸릴 수 있습니다 어떤 주어진 하나 되는 - 이 정말 관련된 알고리즘에 따라 달라집니다 위해 일어날 것 - 특정 예를 들어,이의 경우 것 사이에 다른 최적화의 가능성을 무시하고, 두.Θ(n2)nnn < 100

각각 시간 Θ(n)과 시간이 걸리는 두 개의 주어진 알고리즘 에 대해 다음 중 하나를 보게 될 것입니다.Θ(n2)

• Θ(n)알고리즘 때 느리다 n작고, 그 하나로서 느려지 증가 합니다 (일어나는 경우 , 즉 이상 일정한 계수를 갖는 하나가 더 복잡하다), 또는Θ(n2)n
Θ(n)
• 하나는 항상 느립니다.Θ(n2)

그것은 확실히 비록 수 것을 Θ(n)알고리즘이 느려질 수 있습니다, 다음 하나, 그 하나 다시, 등등으로 증가 할 때까지 이후 그 시점에서, 매우 큰 도착 이 일어날 크게 확률이 낮다하더라도, 하나는 항상 느려집니다.Θ(n2)Θ(n)nnΘ(n2)

약간 더 수학적 용어로 :

하자가 말 알고리즘이 걸리는 일부 작업을 .Θ(n2)cn2c

그리고 Θ(n)알고리즘은 dn일부 d.

이것은 우리가 이것이 0보다 큰 (즉, all에 대해 ) 유지되고 실행 시간이 놓여있는 두 함수가 동일 하다고 가정 할 수 있기 때문에 공식적인 정의 와 일치합니다.nn

귀하의 예제와 라인에서, 당신이 말하는 것 인 경우 c = 1와 d = 100다음, Θ(n)때까지 알고리즘이 느린 것 n = 100시점, 알고리즘이 느려질 것입니다.Θ(n2)

_{( WolframAlpha 제공 )} .

표기 참고 :

기술적으로 big-O는 상한 일뿐입니다. 즉, O(1)알고리즘 (또는 실제로 시간이 걸리거나 더 적은 시간이 걸리는 모든 알고리즘 )도 걸린다고 말할 수 있습니다. 따라서 대신에 타이트 바운드 인 빅 세타 (Θ) 표기법을 사용했습니다. 자세한 정보 는 공식 정의 를 참조하십시오.O(n2)O(n2)

Big-O는 종종 비공식적으로 타이트 바운드로 취급되거나 가르치기 때문에 이미 big-Theta를 알지 못한 채 기본적으로 사용하고있을 수 있습니다.

If we're talking about an upper bound only (as per the formal definition of big-O), that would rather be an "anything goes" situation - the O(n) one can be faster, the O(n2) one can be faster or they can take the same amount of time (asymptotically) - one usually can't make particularly meaningful conclusions with regard to comparing the big-O of algorithms, one can only say that, given a big-O of some algorithm, that that algorithm won't take any longer than that amount of time (asymptotically).

---

Yes, an O(n) algorithm can exceed an O(n²) algorithm in terms of running time. This happens when the constant factor (that we omit in the big O notation) is large. For example, in your code above, the O(n) algorithm will have a large constant factor. So, it will perform worse than an algorithm that runs in O(n²) for n < 10.

Here, n=100 is the cross-over point. So when a task can be performed in both O(n) and in O(n²) and the constant factor of the linear algorithm is more than that of a quadratic algorithm, then we tend to prefer the algorithm with the worse running time. For example, when sorting an array, we switch to insertion sort for smaller arrays, even when merge sort or quick sort run asymptotically faster. This is because insertion sort has a smaller constant factor than merge/quick sort and will run faster.

---

Big O(n) are not meant to compare relative speed of different algorithm. They are meant to measure how fast the running time increase when the size of input increase. For example,

• O(n) means that if n multiplied by 1000, then the running time is roughly multiplied by 1000.
• O(n^2) means that if n is multiplied by 1000, then the running is roughly multiplied by 1000000.

So when n is large enough, any O(n) algorithm will beat a O(n^2) algorithm. It doesn't mean that anything for a fixed n.

---

Long story short, yes, it can. The definition of O is base on the fact that O(f(x)) < O(g(x)) implies that g(x) will definitively take more time to run than f(x) given a big enough x.

For example, is a known fact that for small values merge sort is outperformed by insertion sort ( if I remember correctly, that should hold true for n smaller than 31)

---

Yes. The O() means only asymptotic complexity. The linear algorythm can be slower as the quadratic, if it has same enough large linear slowing constant (f.e. if the core of the loop is running 10-times longer, it will be slower as its quadratic version).

The O()-notation is only an extrapolation, although a quite good one.

---

The only guarantee you get is that—no matter the constant factors—for big enough n, the O(n) algorithm will spend fewer operations than the O(n^2) one.

As an example, let's count the operations in the OPs neat example. His two algoriths differ in only one line:

for (int i = 0; i < n; i++) {       (* A, the O(n*n) algorithm. *)

vs.

for (int i = 0; i < 100; i++) {     (* B, the O(n) algorithm. *)

Since the rest of his programs are the same, the difference in actual running times will be decided by these two lines.

• For n=100, both lines do 100 iterations, so A and B perform exactly the same at n=100.
• For n<100, say, n=10, A does only 10 iterations, whereas B does 100. Clearly A is faster.
• For n>100, say, n=1000. Now the loop of A does 1000 iterations, whereas, the B loop still does its fixed 100 iterations. Clearly A is slower.

Of course, how big n has to get for the O(n) algorithm to be faster depends on the constant factor. If you change the constant 100 to 1000 in B, then the cutoff also changes to 1000.

참고URL : https://stackoverflow.com/questions/22594174/can-an-on-algorithm-ever-exceed-on2-in-terms-of-computation-time