Как оценить и объяснить время работы для этого алгоритма?

Псевдокод:Как оценить и объяснить время работы для этого алгоритма?

s <- 0 
    for i=1 to n do 
     if A[i]=1 then 
      for j=1 to n do 
       {constant number of elementary operations} 
      endfor 
     else 
      s <- s + a[i] 
     endif 
    endfor

где А [I] представляет собой массив из п целых чисел, каждая из которых представляет собой случайное значение от 1 до 6.

Я на потере здесь ... сбор от моих заметок и некоторых других источников в Интернете, я получаю

Т (п) = С1 (н) + С2 + С3 (н) + С4 (н) + С5

где C1 (N) и С3 (N) = для циклов, а C4 (N) = постоянное число элементарных операций. Хотя у меня есть сильное чувство, что я ошибаюсь.

источник

2014-11-05 Wei

Что такое A [i]?Вы никогда не инициализируете его. –

В чем сложность 'A [i]' тоже? –

Ну, только вопрос показывает, что A - это массив из n целых чисел, каждый из которых является случайным значением от 1 до 6 ... – Wei

Вы зацикливаете от 1..n, и каждый цикл ALSO проходит от 1..n (в худшем случае). O (n^2) правильно?

Иными словами: Вы не должны быть , добавив C3 (N). Это было бы так, если бы у вас было два независимых для цикла из 1..n. Но у вас есть вложенный цикл. Вы будете запускать внутренний цикл N раз, а внешний цикл - N раз. N * N = O (n^2).

источник

2014-11-05 16:59:29 aquinas

Так что в основном все, что мне нужно написать, это T (n) = O (N^2)? или я должен добавить третий C3 (N)? – Wei

Когда люди говорят о временной сложности, они ожидают чего-то вроде O (n^2) или O (nlgn). Даже в том случае, когда вы * сделали * две петли из 1..n (не вложенные), вы все равно должны писать O (n) * not * O (n) + O (n). Черт, у вас может быть 50 000 циклов, которые идут от 1..n; еще O (n). – aquinas

Давайте немного подумаем о том, что делает этот алгоритм.

Вы в основном прокручиваете каждый элемент массива хотя бы один раз (внешний для, с i). Иногда, если значение A [i] равно 1, вы снова повторяетесь через весь цикл с помощью j.

В вашем худшем случае вы работаете против массива всех 1.

В этом случае ваша сложность:

время инициализации S
N * (время, чтобы протестировать [я] == 1 + п * Время {константа ...})

Который означает: T = T (s) + n * (T) (t)) = n^2 * T (const) + n * T (test) + T (с). Асимптотически это O (n^2).

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

В этом случае, предполагая равномерное распределение значений в A, вы получите доступ к циклу for j в среднем в 1/6 раза.

Значит, вы получите: - время для инициализации s - n * (время для проверки [i] == 1 + 1/6 * n * время {константа ...} + 5/6 * T (приращение s)

Это означает: T = T (s) + n * (T (test) + 1/6 * n * T (const) + 5/6 * T (inc s)) = 1/6 * n^2 * T (const) + n * (5/6 * T (inc s) + T (test)) + T (s).

Опять же асимптотически это все еще O (n^2), но в соответствии со значением T (inc s) это может быть больше или меньше, чем в другом случае.

Удовольствие: можете ли вы оценить ожидаемый средний пробег время для общего распределения значений в A вместо однородного?

источник

2014-11-05 17:08:03

Как оценить и объяснить время работы для этого алгоритма?

ответ

Смежные вопросы