Немного о нотации в деталях, домашнее задание CS, исключая фактическое назначение

Question

Я сижу здесь с этим заданием в курсе по алгоритмам с массивными наборами данных, и использование нотации Little-Oh запутало меня, хотя я совершенно уверен в Big-Oh.

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

Я знаю из определения, что алгоритм A должен расти асимптотически медленнее, чем o (log n), но я не уверен, означает ли это, что алгоритм должен работать в постоянное время или ему все еще разрешено быть log n при определенных условиях, таких как c = 1 или, если это действительно log (n-1) .

Скажем, алгоритм имеет время выполнения O (log n) , но на самом деле делает две итерации и, следовательно, c = 2, но 2 * log n по-прежнему O (log n) , я прав, когда говорю, что это не относится к Литтл-Ох?

Любая помощь очень ценится, и, если она необходима для разъяснения, я предоставлю задание

Answer 1

Сказать, что f есть 'мало-ой-о г' f = o(g), означает, что частное

|f(x)/g(x)|

приближается к 0, а x приближается к бесконечности. Ссылаясь на ваш пример o(log n), этот класс содержит такие функции, как log x / log (log x), sqrt(log x) и многие другие, поэтому o(log x) определенно не подразумевает O(1). С другой стороны, log (x/2) = log x - log 2, поэтому

log (x/2) / log x = 1 - log 2 / log x -> 1

и log (x/2) не в классе o(log x).

Answer 2

Для Little-Oh, f (x) не должен быть меньше, чем g (x) для всех x. Это должно быть меньше только после определенного значения х. (По вашему вопросу все еще разрешено вести журнал n при определенных условиях.)

Например:

 let f(x) = 5000x and g(x) = x^2

f (x) / g (x) по мере приближения x к бесконечности равно 0, поэтому f (x) означает меньшее из g (x). Однако при x = 1 f (x) больше, чем g (x). Только после того, как x станет больше 5000, g (x) будет больше, чем f (x).

Что на самом деле говорит нам маленький о, так это то, что g (x) всегда растет быстрее, чем f (x). Например, посмотрите, сколько f (x) выросло между x = 1 и x = 2:

 f(1) = 5000
 f(2) = 10000 - f(x) became twice as big

Теперь посмотрите на g (x) в том же интервале:

 g(1) = 1
 g(2) = 4 - g(x) became four times bigger

Эта скорость увеличится еще больше при больших значениях х. Теперь, поскольку g (x) увеличивается с большей скоростью и поскольку мы берем x до бесконечности, в какой-то момент он станет больше, чем f (x). Но это не то, что мало-мальски обеспокоен, это все о скорости изменения.