#time-complexity #big-o
Вопрос:
Это вопрос, который мой преподаватель курса (Структура данных)задал в классном тесте. Каков был бы правильный ответ здесь? Поскольку log n^2 =2 log n , насколько я знаю, во временной сложности это может быть записано как O(log n), поскольку постоянные множители отменяются. Тогда является ли одно лучше другого каким-либо определенным образом?
Ответ №1:
Асимптотически они одинаковы.
Ваши рассуждения верны, O(log n^2) можно упростить до O(log n), и, очевидно, они равны.
Это похоже на то, что у вас есть два алгоритма, которые работают с массивом, первый-O(n), а второй-O(2n). Если вы посмотрите на количество выполненных операций, то вторая выполняет вдвое больше операций, чем первая, но это не важно для асимптотической записи. Они находятся в том же порядке, что и O(n).
В вашем конкретном примере порядок равен O(log n), и их можно считать одинаковыми.
Ответ №2:
Я бы согласился с вами, что любое O(log(x^k)) равно O(log(x)). Вычислительная сложность масштабируется одинаково.