Найти тета-обозначение следующего цикла while

Question

У меня вопрос к домашней задаче:

1. Найдите тэта-обозначение числа раз выполнения оператора x = x + 1.(10 баллов).

i = n
while (i >= 1)
{
   for j = 1 to n
   {
      x = x + 1
   }
   i = i/2
}

Вот что я сделал:

Хорошо, сначала давайте сделаем это проще.Сначала мы найдем порядок роста:

while (i >= 1)
{
   x = x + 1
   i = i/2
}

, который имеет порядок роста O(log(n)) фактически логическая база 2

другой внутренний цикл for будет выполняться n раз, поэтому алгоритм долженбыть порядка:

O(log(n)*n)

---

Часть, в которой я запутался, заключается в том, что я должен найти тэта-обозначение, а НЕ big-O.Я знаю, что тэта-запись предполагает ограничение функции по верхнему и нижнему пределам.Будет ли правильный ответ Theta(log(n)*n)?

Я нашел ответ в этой ссылке , но я не знаю, как вы получите этот ответ.Почему они утверждают, что ответом является Theta (n)?

Answer 1

Перефразируя ваш фрагмент кода более формальным способом, чтобы его можно было легко представить с помощью сигма-нотации:

for (i = n; i >= 1; i = i/2 ) {
    for j = 1; j <= n; j ++) {
        x = x + 1; // instruction of cost 'c'
    }
}

Получаем:

Answer 2

Теперь вы должны доказать, что это также Omega(nlogn).

Я не буду точно показывать, как это делать, поскольку это домашняя работа, но с теми же принципами, которые вы показываете O(nlogn). Вам нужно показать [неформально объяснение:], что асимптотическое поведение функции растет как минимум так же быстро , как nlogn. [для больших O вы показываете, что он растет максимум со скоростью nlogn].

Помните, что если функция является одновременно O(nlogn) и Omega(nlogn), то это Тета (nlogn) [и наоборот]

стр. С. Ваша догадка верна, легко показать, что это не Omega(n), и, следовательно, это не Theta(n)

p.s. 2 : Я думаю, что автор другого ответа перепутал с другой программой:

i = n
while (i >= 1)
{
   for j = 1 to i //NOTE: i instead of N here!
   {
      x = x + 1
   }
   i = i/2
}

Вышеуказанная программа действительно Theta(n), но она отличается от той, которую вы предоставили.

Answer 3

Как @ amit упоминает, что у меня уже есть верхний предел функции, и это Big-O, которое фактически является O (n * lgn).если я построю таблицу этой функции, я получу что-то вроде:

n   n*lng
1   0
2   2
3   4.754887502
4   8
5   11.60964047
6   15.509775
7   19.65148445
8   24
9   28.52932501
10  33.21928095

, потому что это big-O, то это означает, что действительная функция будет ограничена этими значениями.Другими словами, реальные значения должны быть меньше значений в таблице.например, взяв точку для установки, когда n=9 мы знаем, что ответ должен быть меньше или равен 28.52932501, посмотрев на таблицу

Так что теперь нам не хватает найти Омегу, а это другойсвязаны.Я думаю, что функция нижней границы должна быть Omega(n), и тогда мы получим таблицу

n   Omega(n)
1    1
2    2
3    3
4    4
5    5
6    6
7    7
8    8
9    9
.......

, так что это будет другая граница.Если мы снова возьмем точку, например, где n = 9, то это даст нам 9. Это означает, что наша реальная функция должна дать нам значение, большее или равное 9. На основании нашей функции big-O мы также знаем, что она должна бытьменьше или равно 28.52932501