Big O, как вы рассчитываете / приближаете это?

Большинство людей со степенью в CS наверняка знают, что Big O означает . Это помогает нам измерить, насколько (не) эффективен алгоритм на самом деле, и если вы знаете в , к какой категории относится проблема, которую вы пытаетесь решить, в , вы можете выяснить, можно ли еще выжать эту небольшую дополнительную производительность. 1

Но мне любопытно, как вы вычисляете или приближаете сложность ваших алгоритмов?

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

вопрос задан 6.08.2008
sven
11004 репутация

22 ответов


  • 190 рейтинг

    Большой O дает верхнюю границу временной сложности алгоритма. Обычно он используется в сочетании с обработкой наборов данных (списков), но может использоваться в другом месте.

    Несколько примеров того, как это используется в C-коде.

    Скажем, у нас есть массив из n элементов

    int array[n];
    

    Если бы мы хотели получить доступ к первому элементу массива, это было бы O (1), поскольку не имеет значения, насколько велик массив, всегда требуется одинаковое постоянное время для получения первого элемента.

    x = array[0];
    

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

    for(int i = 0; i < n; i++){
        if(array[i] == numToFind){ return i; }
    }
    

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

    Когда мы доберемся до вложенных циклов:

    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            array[j] += 2;
        }
    }
    

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

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

    ответ дан DShook, с репутацией 9189, 6.08.2008
  • 7 рейтинг

    Знакомство с алгоритмами / структурами данных, которые я использую, и / или быстрый краткий анализ итерационных вложений. Сложность заключается в том, что вы вызываете библиотечную функцию, возможно, несколько раз - вы часто можете быть не уверены в том, вызываете ли вы функцию излишне время от времени или какую реализацию они используют. Возможно, библиотечные функции должны иметь показатель сложности / эффективности, будь то Big O или какой-либо другой показатель, который доступен в документации или даже IntelliSense .

    ответ дан Matt Mitchell, с репутацией 23867, 6.08.2008
  • 7 рейтинг

    Разбейте алгоритм на части, для которых вы знаете большие обозначения O, и объедините их с помощью больших операторов O. Это единственный способ, которым я знаю.

    Для получения дополнительной информации, посетите страницу 4152340744 Википедии по этому вопросу.

    ответ дан Lasse Vågsæther Karlsen, с репутацией 279998, 6.08.2008
  • 0 рейтинг

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

    Это означает, что между алгоритмом в O (n) и алгоритмом в O (n 2 ) самый быстрый не всегда является первым (хотя всегда существует значение n такое, что для задач размера & gt; n, первый алгоритм самый быстрый).

    Обратите внимание, что скрытая константа очень сильно зависит от реализации!

    Кроме того, в некоторых случаях среда выполнения не является детерминированной функцией 3230269583 размера n ввода. Возьмем, к примеру, сортировку с использованием быстрой сортировки: время, необходимое для сортировки массива из n элементов, не является постоянной величиной, а зависит от начальной конфигурации массива.

    Существуют разные временные сложности:

    • Худший случай (обычно самый простой, но не всегда очень значимый)
    • Средний случай (как правило, гораздо сложнее выяснить. , , )

    • . , ,

    Хорошее введение Введение в анализ алгоритмов Р. Седжвик и П. Flajolet.

    Как вы говорите, premature optimisation is the root of all evil и (если возможно) профилирование действительно должны всегда использоваться при оптимизации кода. Это может даже помочь вам определить сложность ваших алгоритмов.

    ответ дан OysterD, с репутацией 4741, 23.08.2008
  • 0 рейтинг

    Как правило, менее полезный, но для полноты картины есть также Big Omega Ω , который определяет нижнюю границу сложности алгоритма, и Big Theta Θ , который определяет как верхнюю и нижняя граница.

    ответ дан Martin, с репутацией 4755, 23.09.2008
  • 0 рейтинг

    Хотя знание того, как рассчитать время Big O для вашей конкретной проблемы, полезно, знание некоторых общих случаев может иметь большое значение для принятия решений в вашем алгоритме.

    Вот некоторые из наиболее распространенных случаев, взятых из http: // en. википедия. org / wiki / Big_O_notation # Orders_of_common_functions :

    O (1) - определение, является ли число четным или нечетным; используя таблицу подстановок постоянного размера или хэш-таблицу

    O (logn) - Поиск элемента в отсортированном массиве с помощью двоичного поиска

    O (n) - поиск элемента в несортированном списке; добавление двух n-значных чисел

    O (n 2 ) - Умножение двух n-значных чисел простым алгоритмом; добавление двух n × n матриц; пузырьковая сортировка или вставка сортировки

    O (n 3 ) - Умножение двух матриц n × n по простому алгоритму

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

    O (n! ) - Решение проблемы коммивояжера с помощью поиска методом грубой силы

    O (n n ) - Часто используется вместо O (n! ), чтобы вывести более простые формулы для асимптотической сложности

    ответ дан Giovanni Galbo, с репутацией 10564, 5.09.2008
  • 0 рейтинг

    Система обозначений Big O полезна, потому что с ней легко работать, и она скрывает ненужные сложности и детали (для некоторого определения ненужных). Один хороший способ понять сложность алгоритмов «разделяй и властвуй» - это метод дерева. Допустим, у вас есть версия быстрой сортировки с медианной процедурой, поэтому вы каждый раз разбиваете массив на идеально сбалансированные подмассивы.

    Теперь создайте дерево, соответствующее всем массивам, с которыми вы работаете. В корне у вас есть исходный массив, корень имеет двух дочерних элементов, которые являются подмассивами. Повторяйте это до тех пор, пока у вас не будет единственных массивов элементов внизу.

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

    Таким образом, мы можем ограничить объем работы O (n * log (n)).

    Тем не менее, Big O скрывает некоторые детали, которые мы иногда не можем игнорировать. Рассмотрим вычисление последовательности Фибоначчи с

    a=0;
    b=1;
    for (i = 0; i 

    и давайте просто предположим, что a и b являются BigIntegers в Java или что-то, что может обрабатывать произвольно большие числа. Большинство людей сказали бы, что это алгоритм O (n) без вздрагивания. Причина в том, что у вас есть n итераций в цикле for, а O (1) работает в стороне цикла.

    Но числа Фибоначчи велики, n-е число Фибоначчи экспоненциально по n, поэтому простое его сохранение займет порядка n байтов. Выполнение сложения с большими целыми числами потребует O (n) объема работы. Таким образом, общий объем работы, выполненной в этой процедуре, составляет

    1 + 2 + 3 +. , , + n = n (n-1) / 2 = O (n ^ 2)

    Итак, этот алгоритм работает в квадратичное время!

    ответ дан sven, с репутацией 11004, 8.08.2008
  • 0 рейтинг

    Я не знаю, как программно решить эту проблему, но первое, что люди делают, это то, что мы выбираем алгоритм для определенных шаблонов по количеству выполненных операций, скажем, 4n ^ 2 + 2n + 1, у нас есть 2 правила:

    1. Если у нас есть сумма терминов, то термин с наибольшим темпом роста сохраняется, а другие термины опускаются.
    2. Если мы имеем произведение нескольких факторов, постоянные факторы опускаются.

    Если мы упростим f (x), где f (x) - формула для числа выполненных операций (4n ^ 2 + 2n + 1, объясненное выше), мы получим значение big-O [O (n ^ 2) в этот случай]. Но это должно было бы учитывать интерполяцию Лагранжа в программе, что может быть трудно реализовать. И что, если реальное значение big-O было O (2 ^ n), и у нас могло бы быть что-то вроде O (x ^ n), поэтому этот алгоритм, вероятно, не был бы программируемым. Но если кто-то докажет, что я неправ, дайте мне код. , , ,

    ответ дан Gavriel Feria, с репутацией 350, 11.05.2013
  • 0 рейтинг

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

    Это имеет несколько преимуществ по сравнению с простым изучением кода. Во-первых, вы можете увидеть, находитесь ли вы в диапазоне, когда время выполнения приближается к асимптотическому порядку. Кроме того, вы можете обнаружить, что некоторый код, который, по вашему мнению, был порядка O (x), действительно является порядком O (x ^ 2), например, из-за времени, потраченного на библиотечные вызовы.

    ответ дан John D. Cook, с репутацией 24102, 11.12.2008
  • 0 рейтинг

    Я думаю об этом с точки зрения информации. Любая проблема состоит в изучении определенного количества битов.

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

    Например, оператор if, имеющий две ветви, одинаково вероятные, имеет энтропию 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Таким образом, его энтропия составляет 1 бит.

    Предположим, вы ищете таблицу из N элементов, например N = 1024. Это 10-битная проблема, потому что log (1024) = 10 бит. Поэтому, если вы можете искать его с помощью утверждений IF, которые имеют одинаково вероятные результаты, необходимо принять 10 решений.

    Вот что вы получаете с помощью бинарного поиска.

    Предположим, вы делаете линейный поиск. Вы смотрите на первый элемент и спрашиваете, хотите ли вы. Вероятности составляют 1/1024, а 1023/1024 - нет. Энтропия этого решения составляет 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * о 0 = о. 01 бит Вы узнали очень мало! Второе решение не намного лучше. Вот почему линейный поиск такой медленный. На самом деле это экспоненциальное количество бит, которые вам нужно выучить.

    Предположим, вы занимаетесь индексацией. Предположим, что таблица предварительно отсортирована по множеству бинов, и вы используете некоторые из всех битов в ключе для индексации непосредственно к записи таблицы. При наличии 1024 бинов энтропия составляет 1/1024 * log (1024) + 1/1024 * log (1024) +. , , для всех 1024 возможных результатов. Это 1/1024 * 10 × 1024 результатов или 10 битов энтропии для этой одной операции индексации. Вот почему поиск по индексу происходит быстро.

    Теперь подумайте о сортировке. У вас есть N предметов, и у вас есть список. Для каждого элемента вы должны найти, куда он попадает в список, а затем добавить его в список. Таким образом, сортировка занимает примерно N раз количество шагов основного поиска.

    Так, сортировки, основанные на бинарных решениях, имеющих примерно одинаково вероятные результаты, все принимают за O (N log N) шагов. Алгоритм сортировки O (N) возможен, если он основан на поиске по индексу.

    Я обнаружил, что почти все проблемы производительности алгоритмов можно рассматривать таким образом.

    ответ дан Mike Dunlavey, с репутацией 35117, 10.03.2009
  • 0 рейтинг

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

    Иногда сложность может возникнуть из-за того, сколько раз что-то вызывается, как часто выполняется цикл, как часто выделяется память и так далее, это еще одна часть, чтобы ответить на этот вопрос.

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

    ответ дан JB King, с репутацией 11694, 14.10.2008
  • 0 рейтинг

    Для 1-го случая внутренний цикл выполняется n-i раза, поэтому общее количество выполнений является суммой для i, идущей от 0 до n-1 (потому что ниже, не ниже или равно) n-i. Вы получите наконец n*(n + 1) / 2, поэтому O(n²/2) = O(n²).

    Для 2-го цикла i находится между 0 и n, включенными для внешнего цикла; тогда внутренний цикл выполняется, когда j строго больше, чем n, что тогда невозможно.

    ответ дан Emmanuel, с репутацией 9173, 31.01.2011
  • 0 рейтинг

    отличный вопрос!

    Если вы используете Big O, вы говорите о худшем случае (подробнее о том, что это значит позже). Кроме того, есть тэта-столица для среднего случая и большая омега для лучшего случая.

    Посетите этот сайт, чтобы получить прекрасное формальное определение Big O: https: // xlinux. NIST. г / папы / HTML / bigOnotation. HTML

    f (n) = O (g (n)) означает, что существуют положительные постоянные c и k, такие что 0 ≤ f (n) ≤ cg (n) для всех n ≥ k. Значения c и k должны быть фиксированы для функции f и не должны зависеть от n.


    Хорошо, теперь, что мы подразумеваем под сложностями «наилучшего» и «худшего»?

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

    Смысл всех этих прилагательных -сложных сложностей состоит в том, что мы ищем способ построить график времени, в течение которого гипотетическая программа выполняется до конца, с точки зрения размера определенных переменных. Однако для многих алгоритмов можно утверждать, что не существует единственного времени для определенного размера ввода. Обратите внимание, что это противоречит основному требованию функции, любой вход должен иметь не более одного выхода. Итак, мы придумали несколько функций для описания сложности алгоритма. Теперь, даже если поиск в массиве размера n может занимать различное количество времени в зависимости от того, что вы ищете в массиве, и пропорционально n, мы можем создать информативное описание алгоритма, используя лучший случай, средний случай и классы наихудшего случая.

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

    ответ дан Samy Bencherif, с репутацией 590, 20.08.2016
  • 0 рейтинг

    Что касается того, «как вы рассчитываете» Big O, это является частью Теория сложности вычислений . Для некоторых (многих) особых случаев вы можете использовать некоторые простые эвристики (например, подсчет числа циклов для вложенных циклов), особенно. когда все, что вам нужно, это какая-либо верхняя оценка, и вы не возражаете, если она слишком пессимистична - наверное, именно в этом и заключается ваш вопрос.

    Если вы действительно хотите ответить на свой вопрос для любого алгоритма, лучшее, что вы можете сделать, это применить теорию. Помимо упрощенного анализа «наихудшего случая» я нашел Амортизированный анализ очень полезным на практике.

    ответ дан Suma, с репутацией 20475, 10.03.2009
  • 0 рейтинг

    Видя ответы здесь, я думаю, мы можем заключить, что большинство из нас действительно приближают порядок алгоритма к , глядя на него и используют здравый смысл вместо того, чтобы вычислять его, например, с помощью мастер-метода , как мы думали в университете. С учетом вышесказанного я должен добавить, что даже профессор призвал нас (позже) на самом деле подумать об этом вместо того, чтобы просто рассчитать его.

    Также хотелось бы добавить, как это делается для рекурсивных функций :

    предположим, что у нас есть такая функция (, код схемы ):

    (define (fac n)
        (if (= n 0)
            1
                (* n (fac (- n 1)))))
    

    , который рекурсивно вычисляет факториал данного числа.

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

    Итак, производительность для тела: O (1) (постоянная).

    Затем попытайтесь определить это для числа рекурсивных вызовов . В этом случае у нас n-1 рекурсивных вызовов.

    Таким образом, производительность для рекурсивных вызовов: O (n-1) (порядок равен n, так как мы отбрасываем незначительные части).

    Затем соедините эти два, и вы получите производительность для всей рекурсивной функции:

    1 * (n-1) = O (n)


    Петр , чтобы ответить ваши поднятые вопросы; метод, который я здесь опишу, на самом деле справляется с этим довольно хорошо. Но имейте в виду, что это все еще приближение 3230269583 , а не полный математически правильный ответ. Описанный здесь метод также является одним из методов, которым нас учили в университете, и, если я правильно помню, использовался для гораздо более сложных алгоритмов, чем факториал, который я использовал в этом примере.
    Конечно, все зависит от того, насколько хорошо вы сможете оценить время выполнения тела функции и количество рекурсивных вызовов, но это верно и для других методов.

    ответ дан sven, с репутацией 11004, 7.08.2008
  • 0 рейтинг

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

    В качестве очень простого примера скажем, что вы хотели сделать проверку работоспособности на скорости. Сортировка списка NET Framework. Вы можете написать что-то вроде следующего, а затем проанализировать результаты в Excel, чтобы убедиться, что они не превышают кривую n * log (n).

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

    int nCmp = 0;
    System.Random rnd = new System.Random();
    
    // measure the time required to sort a list of n integers
    void DoTest(int n)
    {
       List lst = new List(n);
       for( int i=0; ib)?1:0)); }
    
       System.Console.Writeline( "{0},{1}", n, nCmp );
    }
    
    
    // Perform measurement for a variety of sample sizes.
    // It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
    for( int n = 0; n<1000; n++ )
       DoTest(n);
    
    ответ дан Eric, с репутацией 8220, 5.09.2008
  • 0 рейтинг

    Давайте начнем с начала.

    Прежде всего, примите принцип, что некоторые простые операции с данными могут быть выполнены в O(1) году, то есть во времени, которое не зависит от размера ввода. Эти примитивные операции в C состоят из

    1. Арифметические операции (например, г. + или%).
    2. Логические операции (например, г. & amp; & amp;).
    3. Операции сравнения (e. г. & lt; =).
    4. Операции доступа к структуре (e. г. индексирование массива как A [i], или указатель опускание с помощью - & gt; оператор).
    5. Простое присваивание, такое как копирование значения в переменную.
    6. Вызовы библиотечных функций (например, г. , scanf, printf).

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

    1. Операторы присваивания, которые не включают вызовы функций в своих выражениях.
    2. Читайте заявления.
    3. Написать операторы, которые не требуют вызовов функций для оценки аргументов.
    4. Выражения перехода ломают, продолжают, переходят и возвращают выражение, где выражение не содержит вызов функции.

    В C многие циклы for формируются путем инициализации переменной индекса некоторым значением и увеличивая эту переменную на 1 каждый раз вокруг цикла. Цикл for заканчивается, когда индекс достигает некоторого предела. Например, цикл for

    for (i = 0; i < n-1; i++) 
    {
        small = i;
        for (j = i+1; j < n; j++)
            if (A[j] < A[small])
                small = j;
        temp = A[small];
        A[small] = A[i];
        A[i] = temp;
    }
    

    использует индексную переменную i. Увеличивает i на 1 каждый раз вокруг цикла и итераций остановитесь, когда я достигну n - 1.

    Однако, на данный момент, сосредоточимся на простой форме цикла for, где разница между конечными и начальными значениями, разделенная на величину, на которую увеличивается индексная переменная, говорит нам, сколько раз мы обходим цикл , Это количество является точным, если нет способов выйти из цикла с помощью оператора jump; в любом случае это верхняя граница числа итераций.

    Например, цикл for выполняет итерации ((n − 1) − 0)/1 = n − 1 times, поскольку 0 - начальное значение i, n - 1 - самое высокое значение, достигнутое i (i. е. , когда я достигает n − 1, цикл останавливается, итераций с i = n − 1 не происходит, и добавляется 1 чтобы я на каждой итерации цикла.

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


    Теперь рассмотрим этот пример:

    (1) for (j = 0; j < n; j++)
    (2)   A[i][j] = 0;
    

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

    Точно так же мы можем ограничить время выполнения внешнего цикла, состоящего из строк (2) - (4), что составляет

    (2) for (i = 0; i < n; i++)
    (3)     for (j = 0; j < n; j++)
    (4)         A[i][j] = 0;
    

    Мы уже установили, что цикл линий (3) и (4) занимает O (n) времени. Таким образом, мы можем пренебречь временем O (1), чтобы увеличить i и проверить, является ли i & lt; п в каждая итерация, заключая, что каждая итерация внешнего цикла занимает O (n) времени.

    Инициализация i = 0 внешнего цикла и (n + 1) -й тест условия я & lt; n также займет O (1) время и им можно пренебречь. Наконец, мы видим, что мы идем вокруг внешнего цикла n раз, принимая O (n) время для каждой итерации, давая в итоге O(n^2) время работы.


    Более практичный пример.

    enter image description here

    ответ дан ajkn1992, с репутацией 4088, 2.02.2014
  • 0 рейтинг

    Я ассистент профессора в моем местном университете по курсу Структуры данных и алгоритмы. Я сделаю все возможное, чтобы объяснить это здесь простыми терминами, но имейте в виду, что эта тема займет у моих студентов пару месяцев, чтобы наконец понять. Вы можете найти больше информации о Главе 2 книги «Структуры данных и алгоритмы в Java» .


    Не существует механической процедуры , которую можно использовать для получения BigOh.

    В качестве «кулинарной книги», чтобы получить BigOh из фрагмента кода, вам сначала нужно понять, что вы создаете математическую формулу, которая подсчитывает, сколько шагов вычислений выполнено с учетом ввода некоторого размера.

    Цель проста: сравнить алгоритмы с теоретической точки зрения без необходимости выполнения кода. Чем меньше количество шагов, тем быстрее алгоритм.

    Например, предположим, у вас есть этот кусок кода:

    int sum(int* data, int N) {
        int result = 0;               // 1
    
        for (int i = 0; i < N; i++) { // 2
            result += data[i];        // 3
        }
    
        return result;                // 4
    }
    

    Эта функция возвращает сумму всех элементов массива, и мы хотим создать формулу для подсчета вычислительной сложности этой функции:

    Number_Of_Steps = f(N)
    

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

    Number_Of_Steps = f(data.length)
    

    Параметр N принимает значение data.length. Теперь нам нужно актуальное определение функции f(). Это делается из исходного кода, в котором каждая интересующая строка пронумерована от 1 до 4.

    Существует много способов расчета BigOh. С этого момента мы будем предполагать, что каждое предложение, которое не зависит от размера входных данных, принимает постоянное число вычислительных шагов в C.

    Мы собираемся добавить индивидуальное количество шагов функции, и ни объявление локальной переменной, ни оператор return не зависят от размера массива data.

    Это означает, что в строках 1 и 4 выполняется количество шагов в C, и функция выглядит примерно так:

    f(N) = C + ??? + C
    

    Следующая часть должна определить значение оператора for. Помните, что мы рассчитываем количество вычислительных шагов, то есть тело инструкции for выполняется N раз. Это то же самое, что добавить C, раз N:

    f(N) = C + (C + C + ... + C) + C = C + N * C + C
    

    Не существует механического правила для подсчета того, сколько раз выполняется тело for, вам нужно посчитать его, посмотрев, что делает код. Чтобы упростить вычисления, мы игнорируем части инициализации, условия и приращения переменной оператора for.

    Чтобы получить фактическое значение BigOh, нам понадобится Асимптотический анализ функции. Это примерно сделано так:

    1. Убери все константы C.
    2. Из f() получить полиномия в его standard form.
    3. Разделите члены полинома и отсортируйте их по скорости роста.
    4. Оставьте тот, который становится больше, когда N приближается к infinity.

    У нашего f() есть два термина:

    f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1
    

    Удаление всех констант и избыточных частей C:

    f(N) = 1 + N ^ 1
    

    Так как последний член является тем, который увеличивается, когда f() приближается к бесконечности (подумайте о ограничивает ), это аргумент BigOh, а функция sum() имеет значение BigOh:

    O(N)
    

    Есть несколько хитростей, чтобы решить некоторые хитрые: используйте суммирования , когда можете.

    В качестве примера этот код может быть легко решен с помощью суммирования:

    for (i = 0; i < 2*n; i += 2) {  // 1
        for (j=n; j > i; j--) {     // 2
            foo();                  // 3
        }
    }
    

    Первое, что вам нужно было спросить, это порядок исполнения foo(). Хотя обычно это O(1), вы должны спросить об этом своих профессоров. O(1) означает (почти, в основном) константу C, не зависящую от размера N.

    Утверждение for в предложении номер один сложно. Хотя индекс заканчивается на 2 * N, приращение делается на два. Это означает, что первые for выполняются только за N шагов, и нам нужно разделить счет на два.

    f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
         = Summation(i from 1 to N)( ... )
    

    Предложение № для двух еще сложнее, поскольку зависит от значения i. Посмотрите: индекс i принимает значения: 0, 2, 4, 6, 8,. , , , 2 * N, а второй for исполняется: N раз первый, N - 2 второй, N - 4 третий. , , до этапа N / 2, на котором второй for никогда не выполняется.

    По формуле это означает:

    f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )
    

    Опять же, мы считаем количество шагов . И по определению, каждое суммирование всегда должно начинаться с единицы и заканчиваться числом, большим или равным единице.

    f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )
    

    (Мы предполагаем, что foo() O(1) и принимает C шагов. )

    У нас проблема здесь: когда i принимает значение N / 2 + 1 вверх, внутреннее суммирование заканчивается отрицательным числом! Это невозможно и неправильно. Нам нужно разделить суммирование на две части, являясь поворотной точкой в ​​момент, когда i занимает N / 2 + 1.

    f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )
    

    После поворотного момента i > N / 2 внутренний for не будет выполнен, и мы предполагаем постоянную сложность выполнения C для его тела.

    Теперь суммы могут быть упрощены с использованием некоторых правил идентификации:

    1. Суммирование (ш от 1 до N) (C) = N * C
    2. Суммирование (w от 1 до N) (A (+/-) B) = Суммирование (w от 1 до N) (A) (+/-) Суммирование (w от 1 до N) (B)
    3. Суммирование (w от 1 до N) (w * C) = C * Суммирование (w от 1 до N) (w) (C является константой, независимой от w)
    4. Суммирование (w от 1 до N) (w) = (N * (N + 1)) / 2

    Применение некоторой алгебры:

    f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )
    
    f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )
    
    f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )
    
    f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )
    
    => Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )
    
    f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )
    
    f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )
    
    => (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 
    
       (N / 2 - 1) * (N / 2) / 2 = 
    
       ((N ^ 2 / 4) - (N / 2)) / 2 = 
    
       (N ^ 2 / 8) - (N / 4)
    
    f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )
    
    f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )
    
    f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )
    
    f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)
    
    f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)
    
    f(N) = C * ( N ^ 2 / 4 ) + C * N
    
    f(N) = C * 1/4 * N ^ 2 + C * N
    

    И BigOh это:

    O(N²)
    
    ответ дан vz0, с репутацией 25291, 31.01.2011
  • 0 рейтинг

    Если ваша стоимость является полиномом, просто оставьте член высшего порядка без его множителя. E. г. :

    O ((n / 2 + 1) * (n / 2)) = O (n 2 /4 + n / 2) = O (n 2 /4) = O (n 2 )

    Это не работает для бесконечных серий, заметьте. Единого рецепта для общего случая не существует, хотя для некоторых общих случаев применяются следующие неравенства:

    O (log N ) & lt; O ( N ) & lt; O ( N log N ) & lt; O ( N 2 ) & lt; O ( N k ) & lt; O (e n ) & lt; O ( n ! )

    ответ дан Marcelo Cantos, с репутацией 140701, 31.01.2011
  • 0 рейтинг

    Что часто упускают из виду, так это ожидаемое поведение ваших алгоритмов. Это не меняет Big-O вашего алгоритма , но оно относится к утверждению «преждевременная оптимизация». , , , "

    Ожидаемое поведение вашего алгоритма - очень глупо - насколько быстро вы можете ожидать, что ваш алгоритм будет работать с данными, которые вы, скорее всего, увидите.

    Например, если вы ищете значение в списке, это O (n), но если вы знаете, что большинство списков, которые вы видите, имеют ваше значение заранее, типичное поведение вашего алгоритма быстрее.

    Чтобы по-настоящему понять это, вам нужно уметь описать распределение вероятностей вашего «пространства ввода» (если вам нужно отсортировать список, как часто этот список уже будет отсортирован? как часто это полностью полностью изменено? как часто это в основном сортируется? ) Не всегда возможно, что вы это знаете, но иногда вы знаете.

    ответ дан Baltimark, с репутацией 4077, 10.03.2009
  • 0 рейтинг

    В основном, вещь, которая возникает в 90% случаев, это просто анализ циклов. У вас есть одинарные, двойные, тройные вложенные циклы? У вас есть O (n), O (n ^ 2), O (n ^ 3) время выполнения.

    Очень редко (если вы не пишете платформу с обширной базовой библиотекой (как, например,. NET BCL или C ++ STL) вы столкнетесь с чем-то более сложным, чем просто просмотр ваших циклов (для операторов, while, goto и т. Д.). , , )

    ответ дан Adam, с репутацией 14702, 14.08.2008
  • 0 рейтинг

    Для кода A внешний цикл будет выполняться n + 1 раз, время '1' означает процесс, который проверяет, соответствует ли i требованию. И внутренний цикл работает n раз, n-2 раза. , , , Таким образом, 0 + 2 +. , + (n-2) + n = (0 + n) (n + 1) / 2 = O (n²).

    Для кода B, хотя внутренний цикл не будет вмешиваться и выполнять foo (), внутренний цикл будет выполняться n раз, в зависимости от времени выполнения внешнего цикла, которое равно O (n)

    ответ дан laynece, с репутацией 81, 31.01.2011