Значок Big O (сложность) следующего кода?

-1

Мне просто интересно, что такое o для кода ниже:Значок Big O (сложность) следующего кода?

Я думаю O (n). Ребята, что вы думаете? Спасибо за помощь!

for(w = Length ; w >= 0 ; w = w/2){ 
    for(i = Length ; i >= 0 ; --i){ 
     if( randomNumber() == 4 ) 
     return 
    } 
}

источник

2015-05-05 John

Как вы думаете, что это такое? –

Подсказка: у вас есть вложенные циклы и нет особых ограничений на то, насколько велика граница цикла, и нет указания на то, насколько вероятным является случайный номер 4. –

Зависит от 'randomNumber()': from 'O (1)' if, скажем, самый первый 'randomNumber() == 4' до' O (Length ** 2) ', если' randomNumber() 'никогда не равен 4; поэтому 'O (Length)' просто * возможно * –

Поскольку вы просите за Big O нотаций, что в худшем случае временной сложность, ответ:

O(n^x), где х знаменатель используется в внешнепризматическом цикле.

источник

2015-05-05 16:03:32 Jerry

Так квадратичное время выполнения? Это правильно, но вы можете иметь более жесткую привязку, если переменные являются целыми числами. – Alex

Собственно, верхняя граница O (2^n) также правильна, поскольку в любом случае она больше, чем время выполнения. – Alex

Это похоже на присвоение класса, поэтому я не отвечаю на него, но просто даю вам несколько указателей (домашняя работа не должна выполняться путем копирования задания в Интернет;)). Также задание является неполным. Я надеюсь, что ваш преподаватель/преподаватель не дал этого так.

недостающее информация:

Вы ищете худшем случае выполнения или среднее время выполнения дела? Big-O может использоваться для обоих. [первоначально я включил наилучшее время выполнения, но это делается с большой омегой, как указал Джерри в комментариях)
Еще одна недостающая часть - это тип данных переменных. Если они удваиваются, это занимает намного больше времени, пока w = w/2 равно 0, чем с целыми числами.

наихудшего случая выполнения:

Внутренний цикл имеет I = I-1, так что он выполнен раза длины. Это дает вам O (n) для внутреннего цикла.

Это уже показывает, что ваша оценка неверна. Это должно быть количество исполнений внешнего цикла TIMES - количество исполнений внутреннего цикла, поэтому оно должно быть более линейным (если только внешний цикл не имеет постоянного количества исполнений).

Внешняя петля имеет w = w/2, поэтому в терминах длины, как долго это должно быть 0? Это дает вам, как часто выполняется внешний цикл. И, путем умножения, общее количество казней.

Чем это случайный номер(). Как я уже сказал, я беру на себя худший анализ, худший случай ясно, что его никогда нет 4, и поэтому мы можем игнорировать это возвращение.

в среднем случае выполнения:

Анализ для петель не меняется. Для randomNumber() нам нужно оценить, сколько времени это займет, пока вероятность НЕ, имеющая 4, достаточно мала. Тем не менее, у меня недостаточно информации о randomNumber(), чтобы сделать это.

наилучшего случай выполнение [должна быть большая омега, а не большие о]:

В лучшем случае, randomNumber() возвращает 4 по первому зову. Таким образом, наилучшее время выполнения является постоянным, O (1).

источник

2015-05-05 16:13:49 Alex

Лучший случай представлен как Big Omega, not Big O – Jerry

Значок Big O (сложность) следующего кода?

ответ

Смежные вопросы