Деблиотекация Little-OH, домашнее задание CS, исключая фактическое задание

Question

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

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

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

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

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

Answer 1

Сказать f это «маленький о-о-g» 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. Он должен быть меньше только после определенного значения x. (Для вашего вопроса все еще разрешено быть логическим при определенных условиях.)

Например:

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

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

То, что Little-O действительно говорит нам, так это то, что 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

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