Блог

Главная - Вопросы по программированию - Нотация Big O (алгоритмы)

Нотация Big O (алгоритмы)

#java #algorithm #time-complexity #big-o

#java #алгоритм #сложность по времени #big-o

Вопрос:

Привет, я новичок в нотации Big O, и у меня возникли проблемы с указанием big O для следующего, если кто-нибудь может любезно объяснить мне, как это решить, пожалуйста

 int sum=1;
for(int count=n; count>0; count/=2) {
    sum=sum*count;
}

Ответ №1:

Поскольку каждый раз count делится на 2, это будет Theta(log n) (от n до 0 ). Следовательно, он O(log(n)) также находится внутри.

Комментарии:

1. Почему theta является ответом для Big O?

2. @GiorgiTsiklauri Основываясь на Theta определении, если f(n) оно in Theta(g(n)) , оно O(g(n)) также будет in .

3. В данном случае это правда. Я хотел указать это и в вашем ответе, что вы и сделали.

4. @GiorgiTsiklauri все время, это правда. Как я уже сказал, это связано с определением Theta и O , и это можно доказать математически.

Ответ №2:

В первой строке код будет выполняться один раз, поэтому для него сложность равна O (1). Во второй строке цикл for будет выполняться до count> 0, и мы видим, что он будет делиться на 2 при каждом запуске цикла, и поэтому он будет продолжаться непрерывно бесконечное время. Таким образом, в принципе, вы не можете применять нотацию Big O в бесконечном цикле. И поэтому вы также не можете применять big O к коду внутри цикла. Итак, если существует какое-либо O (бесконечное), то это может быть ответ, но он не будет существовать. Таким образом, вы не можете определить временную сложность до тех пор, пока n<=0. если n<=0, то код будет выполняться только один раз, а сложность будет O (1).

Ответ №3:

количество уменьшается вдвое за каждую итерацию. Если n = 64 :

 step1 => count = 64
step2 => count = 32
step3 => count = 16
...

Следовательно, его наихудший сценарий имеет O(log n) временную сложность.

Однако в этом случае тело вашего цикла имеет постоянное количество операций, поэтому сценарии наилучшего, наихудшего и среднего случая одинаковы, и:

 Ω(log n) = Θ(log n) = O(log n)