Время выполнения функции для поиска (n/2^k) -го элемента списка размера n?

Question

Я могу представить себе только два случая: когда 2^k приближается к n (скажем, если 2^k == n), то требуется количество шагов n/n или 1, поэтому он имеет время выполнения O (1).

Однако, если 2^k мало (скажем, если 2^k == 1), то требуются n шагов, поэтому он имеет время выполнения O (n).

По существу, если 2^k может быть записано в терминах n, то требуемое количество шагов является целым числом, поэтому оно имеет время выполнения O (1). Если 2^k не может быть записано в терминах n, оно имеет время выполнения O (n).

Оба эти случая являются наихудшими; для любого неизвестного и, возможно, большого n эти временные интервалы все еще сохраняются. Существует ли ситуация, в которой 2^k не может быть квалифицирована как намного меньше, чем n или близко к n?

Представьте, что вы должны были написать (возможно, очень длинную) таблицу, содержащую времена выполнения функции для значений k таких, что (n/2^k)> = 1. Когда k начинается с 0 и увеличивается, run-times - O (1), но поскольку k начинается с большого значения и уменьшается, время выполнения O (n). Существует ли теоретическая точка, в которой время выполнения переключается с O (1) на O (n)?

Или я просто не понимаю «основную идею» анализа Big-O?

EDIT: Линейный поиск предполагается

Answer 1

Вы пропустили основную идею анализа большой-O. Всегда есть предположение (обычно неустановленное), что вы смотрите на предел, поскольку что-то уходит в бесконечность. Обычно есть только одна переменная, поэтому из контекста ясно, что это переменная, идущая в бесконечность. (К примеру, n^2+23n∈O(n^2) (как n уходит в бесконечность).)

В вашем случае, у вас есть две переменные, n и k. Поэтому, чтобы говорить о big-O, вам нужно количественно определить, что будет бесконечно (это выглядит как n), и что другая переменная делает за это время. Это приводит к двум вашим возможностям: если k является постоянным, так как n переходит в бесконечность, тогда ответ O(n); но если k таково, что n/2^k является постоянным (то есть k=lg(n)-C), тогда ответ O(1). Но есть и другие возможности: если n/2^k=√n (т. Е. k=lg(n)/2), то ответ O(√n).

Так что в зависимости от того, как k растет с n, ответ - между O(1) и O(n).

Answer 2

Однако, если 2^k мало (скажем, если 2^k == 1), то требуются n шагов, поэтому он имеет время выполнения O (n). (1)

По существу, если 2^k может быть записано в терминах n, то требуемое количество шагов является целым числом, поэтому оно имеет время выполнения O (1). Если 2^k не может быть записано через n, оно имеет время выполнения O (n). (2)

(1) Правильно, но (2) неверно.

Прежде всего, у вас есть две переменные. n и k.k: 1 <= 2^k <= n

Если n = 128 и k = 4128/2^4 = 4

Количество шагов 4 не 1.

В общем, если n является степенью 2 сказать 2^x, то число шагов f(n) = 2^х/2^к = 2^(Xk) `

Теперь n = 2^x, используя основные логарифмы, x = lg(n) {Где lg(y) это бревно к основанию 2 у»

f(n) = 2^{lg(n)-k} (1)

время работы является 2^{lg(n)-k}, если п не делится на 2^k, то вы пытаетесь доступом s число с индексом с плавающей запятой, которого не существует.

Предполагая, что вы хотите, чтобы я округлял индекс до ближайшего целого числа. Индексы - это целые числа.

Теперь 1 дает вам простую формулу времени выполнения. Но худший случай, когда k = 0. SInce Big-Oh использует худший случай, мы идем с этим.

f(n) = O(2^{lg(n)-0}) f(n) = O(2^{lg(n)}

Это Анти-журнал lg(n) который снова от базовых знаний логарифм дает нам n.

Поэтому f(n) = O(n)

Q.E.D