Определение большого O цикла с разрывом

#javascript #big-o

Вопрос:

Дана функция, подобная этой, для нахождения простого числа:

 function find_the_prime(number) {
  var found = false;
  for(var i = 0; i < number; i  ) {
    if(number%i == 0) {
      found = true; 
      break;
    }
  }  
  return found;
}

Без разрыва функция в лучшем случае равна O (1), в худшем случае равна O (n), а в общем случае O (n) .

Можете ли вы объяснить, как разрыв влияет на большой o? Это вообще так?

1. Кстати, это не домашнее задание, это просто любопытный инженер, который хочет стать лучше с большим O.

2. Я думаю, что это наихудший сценарий с большими O. . O(n)

3. число%0 ? Ошибка деления на ноль 🙁

4. Этот вопрос, похоже, не по теме, потому что он посвящен информатике и относится к информатике .

Ответ №1:

Ваш код равен O(1) по той простой причине, что он всегда завершается во втором цикле, потому что число%1 == 0.

Если вы исправите свой код на:

 for(var i = 2; i < number; i  ) {

Тогда это будет O (n) по той же причине, что и @zmf.

И без разрыва его правильнее было бы вызывать O(n) даже для «наилучшего случая», потому что он по-прежнему масштабируется вместе с вводом. Наименьший ввод не является «наилучшим случаем», иначе все алгоритмы были бы тривиально наилучшими O(1) .

Итак, это O(n) без перерыва и O(n) с перерывом, но это не значит, что это не очевидно лучше и быстрее с перерывом. Нотация big-O описывает, как алгоритм масштабируется в зависимости от размера входных данных, а не (обязательно) от того, насколько он быстр. Иногда O(n) алгоритм может быть быстрее, чем O(log n) алгоритм для конкретного ввода.

1. Разве тогда это не было бы просто O (3)?

2. @Kith: Нет. 1 In O(1) ссылается на то, что это постоянное время , это не подсчет того, сколько раз оно проходит через цикл. Если вы выполните цикл 10 раз, независимо от размера входных данных, вы все равно будете O(1) .

3. @Kith: Нет. Потому что большие значения n будут повторяться чаще. В лучшем случае они четные и завершаются рано, в худшем случае вам нужно попробовать каждое значение до n-1 . Алгоритм, который использует OP, не очень хорош, потому что он будет тестироваться, например 2 , и 4 даже если он не делится на 2 , он не может быть делимым на 4 .

4. Не обращайте на меня внимания. Я плохо читал функцию. Спасибо. Я просто предположил, что функция находила малое простое число в диапазоне от 0 до N)

5. @Kith Когда вы думаете о нотации O, размер N не имеет значения. Размер N может иметь другие проблемы с производительностью, но при обсуждении O помните, что выражение something равно O(N) означает, что объем обработки, необходимый для выполнения этой функции, будет линейно расти. Алгоритм O (1) будет оставаться постоянным на основе N, а O (n ^ 2) означает, что при каждом увеличении N ваша функция будет занимать в два раза больше времени!

Ответ №2:

Это все равно O (N), даже если это худший случай, O (N) — это то, как вы бы назвали этот алгоритм. Скорость его роста по-прежнему зависит от N.

(Если вы исправите ошибку, которая есть)

Ответ №3:

На самом деле, как ни странно, ваш ответ — O (1) . Независимо от того, какое число вы вводите (если оно> 0), оно всегда будет прерываться на 1