Большой O (logn), журнал основывают e?
Стиль программирования очень важен. Чистый код радует глаз и улучшает пригодность для обслуживания программы. Поэтому это непосредственно связывается с качеством и архитектурой самой программы.
Даже на языке, который вызывает добавление отступа, каждый может действительно, повредил все с плохим стилем. Плохой стиль не может поэтому быть отсутствием добавления отступа или комментариев. На самом деле я редко использую комментарии, я очень скорее предпочитаю docstrings и в целом запись лучшей документации. Я связываю комментарии к маленьким примечаниям, которые Вы распространяете вокруг кода, если Вы действительно видите, что существует что-то, чтобы зафиксировать или задаться вопросом о там.
я рассматривал бы плохой стиль как не разрешение языку программирования сделать часть Вашего материала для Вас. Надлежащий, чисто записанный макрос в месте или два является действительно хорошим стилем, а не плохо.
6 ответов
После выражения в нотации big-O () оба значения верны. Однако при выводе полинома O () в случае двоичного поиска корректным будет только log 2 . Я предполагаю, что это различие было интуитивным вдохновением для начала вашего вопроса.
Кроме того, на мой взгляд, запись O (log 2 N) лучше для вашего примера, потому что она лучше передает вывод времени выполнения алгоритма.
В нотации big-O () постоянные множители удаляются. Преобразование одного логарифма в другой включает умножение на постоянный коэффициент.
Таким образом, O (log N) эквивалентно O (log 2 N) из-за постоянного множителя.
Однако, если вы можете легко набрать журнал 2 N в своем ответе, это более педагогично. В случае поиска по двоичному дереву вы правы, что log 2 N вводится во время вывода среды выполнения big-O ().
Прежде чем выразить результат в виде нотации big-O (), разница очень важна. При выводе полинома, который должен передаваться через нотацию большого O, для этого примера было бы неправильно использовать логарифм, отличный от log 2 N, до применения нотации O (). Как только многочлен используется для передачи среды выполнения наихудшего случая через нотацию big-O (), не имеет значения, какой используется логарифм.
При выводе полинома, который должен передаваться через нотацию большого O, было бы неправильным для этого примера использовать логарифм, отличный от log 2 N, до применения нотации O (). Как только многочлен используется для передачи среды выполнения наихудшего случая через нотацию big-O (), не имеет значения, какой используется логарифм. При выводе полинома, который должен передаваться через нотацию большого O, было бы неправильным для этого примера использовать логарифм, отличный от log 2 N, до применения нотации O (). Как только многочлен используется для передачи среды выполнения наихудшего случая через нотацию big-O (), не имеет значения, какой используется логарифм. Нотация Big O не зависит от логарифмического основания, потому что все логарифмы в разных основаниях связаны постоянным множителем , O (ln n) эквивалентно O (log n) .
На самом деле не имеет значения, какая это база, так как нотация большого O обычно записывается с указанием только асимптотически наивысшего порядка n , поэтому постоянные коэффициенты отпадут . Поскольку другое основание логарифма эквивалентно постоянному коэффициенту, оно излишне.
Тем не менее, я бы, вероятно, предположил логарифм с основанием 2.
Да, когда мы говорим о нотации большого О, основание не имеет значения. Однако с вычислительной точки зрения, когда вы сталкиваетесь с реальной проблемой поиска, это имеет значение.
При развитии интуиции о древовидных структурах полезно понимать, что в двоичном дереве поиска можно искать за O (n log n) время, потому что это высота дерева, то есть в двоичном дереве с n узлами. , глубина дерева равна O (n log n) (основание 2). Если у каждого узла есть три дочерних узла, поиск в дереве все равно можно производить за O (n log n) раз, но с логарифмом по основанию 3. С вычислительной точки зрения количество дочерних узлов каждого узла может иметь большое влияние на производительность (см., Например: текст ссылки )
Наслаждайтесь!
Пол
Технически база не имеет значения, но обычно ее можно рассматривать как базу-2.
Оба верны. Подумайте об этом
log2(n)=log(n)/log(2)=O(log(n))
log10(n)=log(n)/log(10)=O(log(n))
logE(n)=log(n)/log(E)=O(log(n))