这些算法的紧渐近运行时间（Big Theta）是什么？ [英] What would be the tight asymptotic runtime (Big Theta) for these algorithms?

问题描述

问题1

 public void guessWhat1(int N){
  for (int i=N; i>0, i=i/2){
  for (int j=0; j<i*2; j+=1){
  System.out.println("Hello World");
  }
 }
}

第一个循环将运行log（n）。
第二个循环将运行log（n）。

The first loop will run for log(n). The second loop will run for log(n).

上限为O（log ^ 2（n）。什么是大Θ？

The upper bound is O(log^2(n). What would be Big Θ?

问题2

 public void guessWhat2(int N) {
 int i=1, s=1;
 while (s<=N) {
  i += 1;
  s = s + i;
 }
}

此上限为O（n），我不是

The upper bound for this is O(n). I am not quite sure about the Big Θ.

如果有人可以澄清这些问题，那就太好了。谢谢

It would great if someone could clarify on these. Thank You

推荐答案

首先让我们弄清楚符号的定义。

Lets get clear with the definitions of the notations first.

大O ：表示算法的上限。

大Theta ：表示算法的平均边界

第一个问题

public void guessWhat1(int N){
  for (int i=N; i>0, i=i/2){
  for (int j=0; j<i*2; j+=1){
  System.out.println("Hello World");
  }
 }
}

对于i = N，内部循环运行2N次，i = N / 2内部循环运行N次，对于i = N / 4内部循环运行N / 2次.....
，所以总复杂度= O（2N + N + N / 2 + N / 4 + ... + 1）
等于O（N（2 + 1 + 1/2 + 1/4 + .... 1 / N））= O （N（3 + 1/2 + 1/4 + .... 1 / N））

For i=N, inner loop runs 2N times, i=N/2 inner loop runs for N times, for i=N/4 inner loop runs for N/2 times..... so the total complexity = O(2N+N+N/2+N/4+...+1) which is equal to O(N(2+1+1/2+1/4+....1/N))= O(N(3+1/2+1/4+....1/N))

N（3 + 1/2 + 1/4 +。 ... 1 / N）
= N（3 +1-（0.5）^ logN）= O（N（4-1 / N））= O（N）
因此复杂度为O （N），即使在theta表示法中，与上述循环相同的N也会在所有情况下花费相同的时间。

N(3+1/2+1/4+....1/N) = N( 3 + 1 - (0.5)^logN ) = O(N(4-1/N)) = O(N) So the complexity is O(N), even in theta notation its the same N as the above loops takes the same time for all cases.

对于第二个问题

public void guessWhat2(int N) {
 int i=1, s=1;
 while (s<=N) {
  i += 1;
  s = s + i;
 }
}

while循环需要O（sqrt（N）） 。与上面相同，theta表示法也将与big O表示法相同，即sqrt（N）。

The while loop takes O(sqrt(N)). Same as above, here also the theta notation will also be the same as big O notation, which is sqrt(N).

如果输入，theta表示法与big O有所不同有多种情况。让我们举一个插入排序示例 https://en.wikipedia.org/wiki/Insertion_sort 其中N是输入数组的大小。如果已对输入数组进行排序，则需要花费线性时间，但是如果对输入数组进行了反向排序，则需要N ^ 2的时间对数组进行排序。

The theta notation varies from big O if input has multiple cases. Lets take an example of insertion sort https://en.wikipedia.org/wiki/Insertion_sort where N is the size of the input array. If the input array is already sorted it takes linear time, but if the input array is reverse sorted it takes N^2 time to sort the array.

因此，在这种情况下，对于插入排序，时间复杂度为O（N ^ 2）。

So in that case for insertion sort, the time complexity is O(N^2).

最好的情况是theta（N），最坏的情况是theta（N ^ 2）。

For best case it is theta(N) and for worst case its theta(N^2).

这篇关于这些算法的紧渐近运行时间（Big Theta）是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！