сложность полиномиального времени - PullRequest
Новая
       14

сложность полиномиального времени

2 голосов
/ 22 сентября 2011

Здесь этот код от здесь 

ub4 additive(char *key, ub4 len, ub4 prime)
{
  ub4 hash, i;
  for (hash=len, i=0; i<len; ++i) 
    hash += key[i];
  return (hash % prime);
}

Говорят, для этого нужно 5n + 3 инструкции. Как они это рассчитали? Как мне рассчитать это?

Ответы [ 3 ]

3 голосов
/ 22 сентября 2011

Чтобы сделать этот расчет, вам нужна базовая примитивная система.Например, в «Искусстве компьютерного программирования» Кнут использует компьютер MIX для выполнения таких вычислений.Разные базовые компьютеры могут иметь разные инструкции и разные результаты для такого рода расчетов.В вашем конкретном примере общий способ его настройки:

  • hash <- len (1 op) </li>
  • i <- 0 (1 op) </li>
  • i
  • ключ [i] поиск (n операций)
  • хэш + ключ [i] (n операций)
  • хэш<- hash + key (n ops) </li>
  • hash% prime (1 op)

, что в сумме составит 5n + 3.

Вариации могут бытьв соответствии с:

  • объявление / создание двух hash и i может занять много времени.Обычному процессору может не потребоваться дополнительная работа из-за объявлений, например, регистрация / стек хранения.
  • hash += hash + key[i] можно считать одной операцией в базовой системе и т. Д.

Редактировать: Обратите внимание, что такого рода расчеты в основном полезны в качестве мысленных экспериментов на гипотетическом оборудовании.Реальный процессор, скорее всего, не будет вести себя точно так же, как эти вычисления, за исключением очень редких случаев.

1 голос
/ 22 сентября 2011

Внутри вашего цикла у вас есть 5 операций, которые запускают каждую итерацию:

  1. сравнить i<len
  2. получить индекс key[i]
  3. добавление hash + key[i]
  4. назначить на hash
  5. приращение ++i

Ваш цикл выполняется n раз, таким образом 5n

Вне цикла у вас есть 3 операции:

  1. назначить len в хэш hash=len
  2. присвойте 0 в i i=0
  3. исполнить hash % prime

Таким образом, 5n + 3.

0 голосов
/ 22 сентября 2011

Давайте начнем считать инструкции.

  1. hash = len и i = 0 выполняются один раз, несмотря ни на что, поэтому у нас есть как минимум 2 инструкции.
  2. hash% prime и return выполняются как минимум один раз, так что это либо 1, либо 2 инструкции (в зависимости от того, считаете ли вы «return» как инструкцию ... Я подозреваю, что это не так).
  3. Каждая итерация цикла требует i << len, ++ i, key [i], hash + key [i] и hash = hash + key [i]. Поэтому у нас есть 5 инструкций, выполняемых по одному разу для каждой из len (n) итераций цикла. </li>

Суммируя, мы получаем около 2 + (1 или 2) + (4 или 5) n, так что 3 + 4n <= T (n) <= 4 + 5n. 3 + 5n разумно; Точный ответ зависит от того, как вы рассчитываете отдельные инструкции. Более детальная модель может считать простые назначения требующими меньше времени, чем, например, операция по модулю ... </p>

...