Является ли `log (n)` основанием 10?

Да, база меняется в зависимости от того, как она повторяется, но это не имеет значения. Как вы помните, изменение основания логарифма означает умножение его на константу. Поскольку вы упомянули, что читали о нотации Big-O, вы, вероятно, уже знаете, что константы не имеют значения (O(n) такое же, как O(2n) или O(1000n)).

РЕДАКТИРОВАТЬ: чтобы уточнить то, что вы сказали: «Я сталкиваюсь с n log n, что, я думаю, равно n, умноженному на значение log n». Да, ты прав. И если вы хотите знать, почему для этого используется log n, то подумайте о том, что делают алгоритмы типа «разделяй и властвуй» — они делят ввод (на две половины, четыре четверти или десять десятых, в зависимости от алгоритма) во время каждой итерации. Вопрос в том, сколько раз этот ввод может быть разделен, прежде чем алгоритм завершится? Итак, вы смотрите на ввод и пытаетесь найти, сколько раз вы можете разделить его на 2, или на 4, или на 10, пока операция не станет бессмысленной? (если только цель алгоритма не состоит в том, чтобы разделить 0 как можно больше раз). Теперь вы можете привести конкретные примеры, начиная с простых вещей, таких как «Сколько раз можно 8 разделить на 2?» или ""Сколько раз можно 1000 разделить на 10?"

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

По сути, вам просто нужно знать, что log n означает, что при экспоненциальном увеличении n время выполнения (или используемое пространство) увеличивается линейно. Например, если n=10 занимает 1 минуту, то n=100 — 2 минуты, а n=1000 — 3 минуты — примерно. (Обычно это с точки зрения верхних границ, а меньшие факторы игнорируются... но в этом и есть общий смысл.)

n log n - это просто log n, умноженное на n, поэтому время или занимаемое пространство в основном увеличиваются "немного быстрее, чем линейно".

База вообще не при чем. На самом деле люди склонны отказываться от части операций, т.е. если у кого-то есть O(n^4 + 2*n), это часто сокращается до O(n^4). При сравнении алгоритмов необходимо учитывать только наиболее релевантную мощность.
В случае сравнения двух тесно связанных алгоритмов, скажем, O(n^4 + 2*n) с O(n^4 + 3*n), необходимо включить линейную зависимость, чтобы сохранить релевантную информацию.

Рассмотрим подход разделяй и властвуй, основанный на делении пополам: ваше основание равно 2, поэтому вы можете говорить о ld(n). С другой стороны, вы используете O-нотацию для сравнения различных алгоритмов с помощью одной и той же базы. При этом разница между ld, ln и log10 заключается лишь в общем смещении.

Логарифмы и экспоненты являются обратными операциями.

if
x^n = y

then
Logx(y) = n

Например,

10^3 = 1000
Log10 (1000) = 3

Алгоритмы «разделяй и властвуй» работают, разделяя проблему на части, которые затем решаются как независимые проблемы. Также может быть этап объединения, объединяющий части. Большинство алгоритмов «разделяй и властвуй» имеют основание 2, что означает, что они каждый раз сокращают проблему вдвое. Например, Binary Search работает как поиск имени в телефонной книге. Вы переворачиваете на середину и говорите... Имя, которое я ищу, в первой половине или во второй половине? (до или после того, к чему вы перелистнули), затем повторите. Каждый раз, когда вы делаете это, вы делите размер проблемы на 2. Следовательно, это основание 2, а не основание 10.

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

Примеры различных заказов:

O(1)
O(n)
O(n * log n)
O(n^2 * log n)
O(n^3.5)
O(n!)

и Т. Д.

O здесь означает «большое обозначение O», которое в основном обеспечивает верхнюю границу скорости роста функции. Поскольку мы заботимся только о росте функции для больших входных данных... например, мы обычно игнорируем члены более низкого порядка.

n^3 + 2 n^2 + 100 n 

было бы

O(n^3) 

поскольку n ^ 3 является наибольшим членом порядка, он будет доминировать в функции роста для больших значений N.

Когда вы видите O (n * log n), люди просто сокращают ... если вы понимаете алгоритм, это обычно логарифмическая база 2, потому что большинство алгоритмов сокращают проблему вдвое. Однако это может быть логарифмическая база 3, например, если алгоритм разрезает проблему, например, на трети.

Примечание:

В любом случае, если бы вы построили график функции роста, она выглядела бы как логарифмическая кривая. Но, конечно, O(Log3 n) будет быстрее, чем O(Log2 n).

Причина, по которой вы не видите O(log10 n) или O(log3 n) и т. д., заключается в том, что алгоритм не так уж часто работает лучше таким образом. В нашем примере с телефонной книгой вы можете разделить страницы на 3 отдельные трети и сравнить между ними 1-2 и 2-3. Но тогда вы только что сделали 2 сравнения и в итоге узнали, в какой 1/3 находится имя. Однако, если вы просто делили его пополам каждый раз, вы бы знали, в какой 1/4 оно было более эффективным.

В огромном наборе языков программирования, которые я знаю, функция log() должна быть базовой e=2.718281....

В математических книгах иногда это означает основание «десять», а иногда основание «e».

Как указывалось в другом ответе, для нотации big-O не имеет значения, потому что для всей базы x сложность O(log_x (n)) такая же, как O(ln(n)) (здесь log_x означает " логарифм по основанию x", а ln() означает "логарифм по основанию e").

Наконец, обычно при анализе нескольких алгоритмов удобнее считать, что log() действительно является «логарифмом по основанию 2». (Я видел некоторые тексты, использующие этот подход). Очевидно, это связано с двоичным представлением чисел в компьютерах.