Я знаю, что O(log n) относится к итеративному сокращению на фиксированное отношение набора проблем N (в большой записи O), но как я могу рассчитать его, чтобы увидеть, сколько итераций алгоритм с сложностью log N должен был бы сформовать на проблема установлена N перед тем, как сделать (есть один элемент слева)?Как рассчитать O (log n) в большой нотации O?
Вы не можете. Вы не вычисляете точное количество итераций с помощью BigO.
Вы можете «получить» BigO, если у вас есть точная формула для количества итераций.
BIGO только дает информацию о том, что итерации число растет с ростом N, и только для «большой» Н.
больше, ни меньше. С этим вы можете сделать выводы, сколько еще операций/времени будет выполняться алгоритмом, если у вас есть несколько прогонов пробега.
Правда, и спасибо за ответ. Как вы сказали, в том случае, когда вы знаете точную пропорцию, которую задает проблема, вы можете ее получить, но есть ли более эффективный способ сделать это, чем запустить вычисление в цикле while, например: while (N > 1) {N = N/2} или что-то в этом роде? другими словами, есть ли расчет, который вы могли бы сделать на калькуляторе, учитывая точное сокращение заданной задачи для каждой итерации, чтобы точно вычислить, сколько итераций требуется? Благодарю. –
Нет, нет, вы не делаете никаких циклов. Вы преобразовываете петли в суммы и другие математические формулы, а затем да, вы можете рассчитать количество операций. Например, у вас есть операция INSERT, которая принимает «O (log SIZE)» для завершения в структуре данных, например, при добавлении элемента. И у вас есть алгоритм, который должен построить такую структуру данных из элемента N, и вы решите вставлять их один за другим, у вас будет 'Sum over i от 0 до N-1: O (INSERT (i))' => 'Sum над i от 0 до N-1: O (log (i)) '=> из свойств O вы можете« вывести его за пределы »' O (сумма для i от 0 до N-1: log (i)) '. – luk32
Знак большой O показывает только порядковый номер, а не фактическое количество операций, которые выполнял бы этот алгоритм. Если вам нужно вычислить точное число итераций цикла или элементарных операций, вы должны сделать это вручную. Однако в большинстве практических целей точное число не имеет значения - O(log n) сообщает вам, что число. операций будет повышаться логарифмически с повышением n
Из большой нотации вы не можете точно указать, сколько итераций будет выполнять алгоритм, это просто оценка. Это означает, что с небольшими числами различие между log (n) и фактическим числом итераций может значительно отличаться, но чем ближе вы достигаете бесконечности, тем менее значимыми.
Выражаясь словами Тима Роугардны на его курсы по алгоритмам:
Большая-О нотации пытается обеспечить сладкое место для высокого уровня алгоритма рассуждения
Это означает, что она предназначена описать связь между временем выполнения алгоритма и размером его ввода, избегая зависимостей от архитектуры системы, языка программирования или выбранного компилятора.
Представьте, что примечание с большим озоном может обеспечить точное время выполнения, что означало бы, что для любого алгоритма, для которого вы знаете его функцию с большим временем О, вы можете предсказать, как он будет вести себя на какой-либо машине вообще.
С другой стороны, оно сосредоточено на асимптотическом поведении. То есть его описание более точно для больших значений n (поэтому члены младшего порядка вашей временной функции алгоритма игнорируются в примечаниях с большими О-О). Можно предположить, что низкие значения n не требуют, чтобы вы пытались повысить производительность вашего алгоритма.
Если вы сделаете некоторые предположения, вы можете оценить время до постоянного коэффициента. Большое допущение состоит в том, что предельное поведение по мере того, как размер стремится к бесконечности, совпадает с фактическим поведением для размеров проблем, о которых вы заботитесь.
В этом предположении верхняя граница времени для размера N составляет C*log(N) для некоторых постоянных C. Константа будет меняться в зависимости от базы, которую вы используете для вычисления логарифма. Основание не имеет значения, если вы согласны с этим.Если у вас есть измеренное время для одного размера, вы можете оценить C и использовать это, чтобы подсчитать время для другого размера.
Например, предположим, что проблема с размером 100 занимает 20 секунд. Используя общие логарифмы, C равно 10. (Общий журнал 100 равен 2). Это говорит о том, что проблема размера 1000 может занять около 30 секунд, поскольку общий журнал 1000 равен 3.
Однако это очень грубо. Этот подход наиболее полезен для оценки того, может ли алгоритм использоваться для большой проблемы. В такой ситуации вам также необходимо обратить внимание на размер памяти. Как правило, проблема с настройкой будет по меньшей мере линейной по размеру, поэтому ее стоимость будет расти быстрее, чем операция .
O (log n) может быть результатом итеративного уменьшения размера проблемы на любом фиксированном соотношении, а не только на половину. –
@Patricia Shanahan Хм ... Правда ... исправил вопрос :) –