#time-complexity #complexity-theory #logarithm
Вопрос:
Я пытаюсь понять логарифмический порядок обозначения O(log(n)).
В моем онлайн-курсе приведен следующий пример:
Представьте, что у нас есть набор данных из 10 элементов. Мы запускаем алгоритм для этого набора данных, и он выполняет 10 операций. Если мы удвоим размер набора данных до 20 элементов, примерно сколько операций теперь может потребоваться для алгоритма логарифмического порядка?
Я предположил, что log(n) имеет основание 2. таким образом, log2(10)= 3,322. однако ответ для этого примера равен 15.
Кто-нибудь может объяснить, как получить этот ответ, пожалуйста? Спасибо.
P.S. Далее в ответе объясняется, что «Если алгоритм имеет логарифмический порядок, то умножение размера набора данных на коэффициент умножает количество требуемых операций на квадратный корень из n» (т. е. количество требуемых операций увеличивается с квадратным корнем из размера набора данных, это правильно?)
Комментарии:
1. Каков ваш источник для этого заявления? Мне это кажется неправильным.
2. Взятие логарифма 2 из 10 кажется хорошим первым шагом к нахождению правдоподобной характеристической формулы для этого алгоритма. Но почему вы тогда умножаете 10 на эти 3,322? Если бы это было 3,322 операции на единицу, это имело бы почти смысл. Но если бы это было 3,322 операции на элемент, то это было бы постоянное время, а не логарифмическое. Так что это не может быть правильным подходом, не так ли?
3. это из онлайн-курса «Вычисления на Python IV: Объекты и алгоритмы» на Edx. Я предположил, что мне нужно было умножить начальные 10 операций на какой-то коэффициент.
Ответ №1:
На этот вопрос невозможно ответить. Информации недостаточно.
Обозначение Big O не обязательно должно точно отражать поведение функции для небольших чисел. Таким образом, тот факт, что временная сложность равна O(log n), ничего не говорит о том, чего мы должны ожидать для небольших входных данных, таких как 10 или 20 элементов.
Но даже игнорируя это, функция логарифмического масштабирования-это функция, в которой, если вы умножаете входные данные на постоянный коэффициент (например, 2 в этом вопросе), выход (т. Е. Количество операций) увеличивается на некоторую постоянную величину. Невозможно определить последнее только на основе информации, приведенной в вопросе. Это может быть любое положительное число.
Так что, если вопрос в точности такой, как вы здесь написали, то вопрос плохо построен. Если есть способ дать обратную связь, подумайте о том, чтобы сделать это.
Изменить: вы только что добавили эту цитату к вопросу:
Если алгоритм имеет логарифмический порядок, то умножение размера набора данных на коэффициент умножает количество требуемых операций на квадратный корень из n
Это совершенно неправильно. Кто бы это ни написал, он не знает, о чем говорит. Больше об этом нечего сказать.
Комментарии:
1. да, вопрос был сформулирован точно так, как я его здесь написал.. Я думал, что мне нужно использовать 10x (квадратный корень из 2) = 14, чтобы получить ответ, близкий к 15. однако я не могу объяснить, почему. Я только что оставил отзыв по этому самому вопросу.
2. ОК. таким образом, log2(1024) равно 10, а log2( 1050000) равно 20, а log2(32800) = 15. итак, просто взглянув на масштаб этих чисел, невозможно увеличить количество операций с 10 до 15, не так ли? каково было бы ваше лучшее предположение?
3. Существует бесконечно много функций в O(log n), где f(10) = 10. Существует бесконечно много таких, где f(20) = 15, и бесконечно много таких, где f(20) — это все, что вы хотите. Если вы хотите знать, откуда у преподавателя курса 15, вам придется спросить их.
4. Спасибо. на самом деле невозможно сказать, откуда взялось 15 в этом тесте с множественным выбором.