Какой будет жесткая асимптотическая среда выполнения (Big Theta) для этих алгоритмов? - PullRequest
Новая
       5

Какой будет жесткая асимптотическая среда выполнения (Big Theta) для этих алгоритмов?

0 голосов
/ 10 октября 2018

Вопрос 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”);
  }
 }
}

Первый цикл будет запущен для журнала (n).Второй цикл будет выполняться для log (n).

Верхняя граница равна O (log ^ 2 (n). Что будет большим Θ?

Вопрос 2 

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

Верхняя граница для этого - O (n). Я не совсем уверен насчет Большого Θ.

Было бы здорово, если бы кто-то мог прояснить это. Спасибо

1 Ответ

0 голосов
/ 11 октября 2018

Давайте сначала разберемся с определениями обозначений.

Big O : Обозначает верхнюю границу алгоритма.

Большая тета : обозначает среднюю границу алгоритма.

Для вашего первого вопроса 

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))

N (3 + 1/2 + 1/4 + .... 1 / N) = N (3 + 1 - (0,5) ^logN) = O (N (4-1 / N)) = O (N) Таким образом, сложность составляет O (N), даже в тета-нотации тот же N, что и в предыдущих циклах, занимает одинаковое время для всех случаев.

На ваш второй вопрос 

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

Цикл while принимает O (sqrt (N)).Как и выше, здесь также тета-нотация также будет такой же, как и большая О-нотация, то есть sqrt (N).

Тета-нотация отличается от большой О, если входные данные имеют несколько случаев.Давайте рассмотрим пример вставки sort https://en.wikipedia.org/wiki/Insertion_sort, где N - размер входного массива.Если входной массив уже отсортирован, это занимает линейное время, но если входной массив отсортирован в обратном порядке, для сортировки массива требуется N ^ 2 времени.

Таким образом, в этом случае для сортировки вставкой временная сложность равна O (N ^ 2).

В лучшем случае это тета (N), а в худшем случае - тета (N ^ 2).).

...