Как рассчитать O (Log (N))?

Question

Я хочу точно знать, как рассчитать O (Log (N)) для этого примера: у нас есть отсортированный массив из 10 элементов [1 3 4 8 10 15 18 20 25 30] Когда мы делаем обычный поиск, мы имеют сложность O (10), что означает, что мы должны проверять каждый случай массива так, чтобы O (10) = 10. , но если мы выполняем дихотомический поиск, потому что у нас есть отсортированный массив, мы имеем сложность (O (Log (10)), что является результатом этого обозначения O (Log (10)) = ???? я есть missunderstand мы будем использовать логарифм 10 или 2 или что именно? спасибо за помощь

Answer 1

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

Если у вас есть массив из 10 элементов, как вы сказали, и вы выполняете «обычный поиск» (он называется Linear Search), вы повторяете каждый элемент в массив, что означает, что если есть «n» элементов, необходимо проверить элементы n. Таким образом, O (n) не O (10). Если бы это было O (10) [btw, O (10) = O (1)], это означало бы, что он всегда будет принимать 10 итераций или меньше, независимо от того, сколько элементов было в массиве, что не так , Если в вашем массиве было 100 элементов, это займет 100 итераций, поэтому мы скажем, что порядок равен O (n), где n - размер ввода (здесь размер массива).

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

Answer 2

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

• O (1) = O (10) = O (Log (10))
• Основу вашего логарифм не имеет значения, так как изменение базы только вводит постоянный множитель

Answer 3

я есть missunderstand мы будем использовать логарифм 10 или 2 или что именно

Это не имеет значения. Сложность не меняется. Вход основание 2 так же, как:

Log_2(N) = Log(N)/Log(2) 

Оба являются элементами O(Log(N)).

Answer 4

Я думаю, вы смущены тем, почему двоичный поиск является журналом (n) и почему он является базой 2. Подумайте об этом таким образом, на каждом шаге вашего бинарного поиска вы уменьшаете размер ввода на 2. Сколько раз вам нужно это делать? Вам нужно сделать это log n на базу 2 раза, чтобы уменьшить размер выборки до 1.

Например, если у вас есть 4 элемента, первый шаг уменьшает поиск до 2, второй шаг уменьшает поиск до 1 и вы остановитесь.Таким образом, вам нужно было сделать это log (4) на базу 2 = 2 раза. Другими словами, если log n base 2 = x, 2, поднятое до степени x, равно n.

Итак, если вы делаете бинарный поиск, ваша база будет 2. Более ясно, что в вашем случае Log (10) base 2 будет чем-то около 3.3. Вы будете делать максимум 4 сравнения.