Время работы 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 

О (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 

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

Прекратить,

arr[hi] * arr[low] > 10 

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

Это означает, что n = высокий - 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

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

Answer 3

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

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

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

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

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

Answer 4

Общая идея нотации 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 (N), O (N * N), O (logN), O (N!) Или, возможно, некоторая другая степень N. O (N!) На самом деле довольно редка, потому что она настолько неэффективна , что его реализация будет бессмысленной.

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

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

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

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

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

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