BigO время работы на некоторых методах

Question

Хорошо, это все довольно простые методы, и их несколько, поэтому я не хотел просто создавать несколько вопросов, когда они все одинаковы.BigO - моя слабость.Я просто не могу понять, как они приходят с этими ответами.В любом случае вы можете дать мне некоторое представление о вашем мышлении для анализа времени выполнения некоторых из этих методов?Как ты разбиваешь это?Как я должен думать, когда я вижу что-то подобное?(особенно второй, я не понимаю, как это O (1))

Answer 1

function f1:
  loop 3 times
    loop n times

Следовательно, O (3 * n), что фактически является O (n).

---

function f2:
  loop 50 times

O (50) - это O (1).

Мы знаем, что цикл будет повторяться 50 раз, потому что он будет идти до тех пор, пока n = n - (n / 50) не станет 0. Для того чтобы это было правдой, он должен повторяться 50 раз (n - (n / 50)*50 = 0).

---

function f3:
  loop n times
    loop n times

Поэтому O (n ^ 2).

---

function f4:
  recurse n times

Вы знаете это, потому что в худшем случае n = high - low + 1. Не обращайте внимания на +1. Это означает, что n = высокий - низкий.

Для прекращения,

arr[hi] * arr[low] > 10

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

Это означает, что n = high - 0, и мы должны повторяться до n раз.

---

function 5:
  loops ceil(log_2(n)) times

Мы знаем это из-за m/=2.

Например, пусть n = 10. log_2 (10) = 3,3, потолок которого равен 4.

10 / 2 = 
  5 / 2 = 
   2.5 / 2 = 
    1.25 / 2 = 
      0.75

Всего 4 итерации.

Answer 2

Вы получаете анализ n ^ 2 при выполнении цикла внутри цикла, такого как третий метод.Тем не менее, первый метод не анализирует синхронизацию ^ 2, потому что первый цикл определяется как выполняющийся три раза.Это делает выбор времени для первого 3n, но нас не интересуют цифры для Big-O.

Второй вводит интересную парадигму, где, несмотря на тот факт, что у вас есть один цикл, анализ времени по-прежнему O (1).Это потому, что если бы вы составили график времени, необходимого для выполнения этого метода, он бы не работал как O (n) для меньших чисел.Для больших чисел это становится очевидным.

Для четвертого метода у вас есть синхронизация O (n), потому что ваш рекурсивный вызов функции передает lo + 1. Это похоже на то, что вы использовали цикл for и увеличивали с помощью lo ++ / ++се.

Последний имеет O (log n), потому что вы делите свою переменную на два.Просто помните, что все, что напоминает вам о бинарном поиске, будет иметь время входа в систему.

Есть еще одна хитрость для анализа времени.Скажем, у вас был цикл внутри цикла, и внутри каждого из двух циклов вы читали строки из файла или извлекали элементы из стека.На самом деле это будет только метод O (n), потому что в файле есть только определенное количество строк, которые вы можете прочитать, а в стеке есть только определенное количество элементов, которые вы можете извлечь.

Answer 3

Общая идея нотации big-O такова: она дает грубый ответ на вопрос: «Если вам дан набор из N элементов, и вам необходимо выполнить какую-либо операцию над этими элементами, сколько раз будет вам нужно выполнить эту операцию? Я говорю грубый ответ, потому что он (в большинстве случаев) не дает точного ответа «5 * N + 35», а просто «N». Это как стадион. Точный ответ вас не волнует, вы просто хотите знать, насколько плохо будет, когда N станет большим. Поэтому ответы типа O (N), O (N * N), O (logN) и O (N!) Являются типичными, поскольку каждый из них представляет собой своего рода «класс» ответов, которые вы можете сравнить друг с другом. Алгоритм с O (N) будет работать лучше, чем алгоритм с O (N * N), когда N становится достаточно большим, не имеет значения, насколько длительной является сама операция.

Итак, я разбил его так: сначала определите, каким будет N. В приведенных выше примерах это довольно очевидно - это размер входного массива, потому что он определяет, сколько раз мы будем выполнять цикл. Иногда это не так очевидно, а иногда у вас есть несколько входных данных, поэтому вместо просто N вы также получаете M и другие буквы (и тогда ответом будет что-то вроде O (N * M * M)).

Затем, когда я вычислил N, я пытаюсь определить цикл, который зависит от N. На самом деле, эти две вещи часто идентифицируются вместе, так как они в значительной степени связаны друг с другом.

И, наконец, мне нужно выяснить, сколько итераций программа выполнит в зависимости от N. И чтобы упростить задачу, я не пытаюсь их подсчитать, просто пытаюсь распознать типичные ответы - O (1), O (N), O (N * N), O (logN), O (N!) Или, возможно, некоторая другая степень N. O (N!) На самом деле довольно редкий, потому что он настолько неэффективен, что его реализация была бы бессмысленной.

Если вы получите ответ на что-то вроде N * N + N + 1, просто отбросьте меньшие, потому что, опять же, когда N становится большим, остальные больше не имеют значения. И игнорировать, если операция повторяется некоторое фиксированное количество раз. O (5 * N) - это то же самое, что O (N), потому что мы ищем приблизительный уровень.

Добавлено: Как указано в комментариях, вот анализ первых двух методов:

Первый прост. Есть только две петли, внутренняя - O (N), а внешняя просто повторяет это 3 раза. Так что это все еще O (N). (Помните - O (3N) = O (N)).

Второй хитрый. Я не совсем уверен в этом. Посмотрев на него некоторое время, я понял, почему он зацикливается не более 50 раз. Поскольку это вообще не зависит от N, оно считается как O (1). Тем не менее, если вы передадите его, скажем, массив из 10 элементов, все положительные, он будет идти в бесконечном цикле. Это O (∞), я думаю. Так какой это? Я не знаю ...

Я не думаю, что есть формальный способ определения числа биг-О для алгоритма. Это как проблема остановки. На самом деле, если подумать, если бы вы могли универсально определить big-O для фрагмента кода, вы также можете определить, останавливается ли он когда-либо или нет, что противоречит проблеме остановки. Но это только мои размышления.

Как правило, я просто проходил мимо ... не знаю, что-то вроде "чутья". Как только вы «получаете» то, что представляет Big-O, оно становится довольно интуитивным. Но для сложных алгоритмов это не всегда возможно определить. Взять, например, Quicksort. В среднем это O (N * logN), но в зависимости от данных оно может ухудшиться до O (N * N). На вопросы, которые вы получите на экзамене, должны быть четкие ответы.

Answer 4

Второй - 50, потому что большой O является функцией длины входа.То есть, если размер ввода изменяется с 1 миллиона до 1 миллиарда, время выполнения должно увеличиться на 1000, если функция - O (N), и на 1 миллион, если это O (n ^ 2).Однако вторая функция выполняется за время 50 независимо от длины ввода, поэтому она равна O (1).Технически это будет O (50), но константы не имеют значения для большого O.