1 Определить временную и емкостную сложность алгоритмов решения следующих задач при равномерном и логарифмическом весовых критериях

1. Определить временную и емкостную сложность алгоритмов решения следующих задач при равномерном и логарифмическом весовых критериях. г) Вычислить среднее значение элементов массива из n чисел. и) В множестве из n дизъюнктов найти и исключить все дизъюнкты с уникальными литералами. Решение. г) Вычислить среднее значение элементов массива из n чисел. В соответствии с данным методом все элементы массива суммируются, далее сумма делится на их количество. Тогда, используя синтаксис языка Паскаль, можно записать: program Av; begin s := 0 i: = 1 while ( i<=n) do begin s=s+A(i) i := i+1; end; f := s/n; end; Временная сложность при равномерном весовом критерии. Очевидно, что шагом алгоритма следует считать тело цикла. В нём имеем n проходов по циклу. Тогда, общее число шагов в алгоритме равно: n Таким образом, временная сложность алгоритма при равномерном весовом критерии есть O(n). Временная сложность при логарифмическом весовом критерии. Логарифмическая временная сложность складывается из трёх частей. Во-первых, работа со счетчиком i. Так как он выполняет прямой счет от 1 до n, то временная сложность этой операции для i-го прохода цикла основной программы есть log(i). За время всех n проходов: i=2nlogi=logn! Во-вторых, работа с промежуточной суммой. Логарифмическая сложность этой операции на шаге i в худшем случае определяется как i*log(Amax). За все проходы имеем: i=1n(i*log⁡(Amax))=(n*n+12)*log⁡(Amax) И деление: log(MAX(s, n))=(n*n+12)*log⁡(Amax) Тогда суммарная временная сложность при логарифмическом критерии есть: logn!+n*n+12*logAmax+log(MAX(s, n))+ (n*n+12)*log⁡(Amax) Окончательно для временной сложности при логарифмическом весовом критерии имеем: O(MAX(logn!,(n*n+12)*log⁡(Amax))) Емкостная сложность при равномерном весовом критерии. Очевидно определяется размером n массива, поэтому есть O(n). Емкостная сложность при логарифмическом весовом критерии. Определяется с одной стороны размером массива и его элементов, а с другой – емкостью счетчика: log(n)+n*log⁡(Amax) Окончательно имеем O(n*log⁡(Amax)). и) В множестве из n дизъюнктов найти и исключить все дизъюнкты с уникальными литералами. Здесь нужно сперва выписать все встречающиеся литералы с общим количеством их включений. Таким образом получим уникальные литералы (с количеством включений, равным единице). Далее следует пройти по всем дизъюнктам, для каждого проверяя, есть ли в нём неуникальный литерал. Если есть – оставляем, если нет – удаляем. Обозначим массив литералов как Аij, где строки – дизъюнкты, в которых данные литералы содержатся. Его размерность – n на m. , Bk c размерностью n*m – массив дизъюнктов, a Cl с такой же размерностью – их частот. Результирующий массив назовём AA. Тогда, используя синтаксис языка Паскаль, можно записать: program NU; procedure put (inp: string) begin k:=1; f:=0; while B(k) <> “–“ and f<>1 begin if inp=B(k) begin С(k):=С(k)+1; f:=1; end k:=k+1; end if B(k) = “–“ then begin B(k) := inp; C(k) := 1; end end bool function isUniq (inp: integer) begin k:=1; f:=0; while B(k) <> “–“ and f<>1 begin if inp=B(k) and 1=C(k) isUniq:=True else isUniq:=False f:=1; k:=k+1; end end begin for i:=1 to n*m do begin B(i):=“–“; С(i):=0; end for i:=1 to n do for j:=1 to m do put(A(i,j)) ii:=0; for i:=1 to n do begin f:=0; for j:=1 to m do if isUniq(A(i,j)) then f:=1; if f=0 then begin ii:=ii+1; for j:=1 to m do AA(ii,j)=A(i,j) end end end; Временная сложность при равномерном весовом критерии. Наибольшую вложенность циклов наблюдаем при вызове процедуры put. Следовательно, наиболее значимая часть числа шагов в алгоритме равна: n*m*(n*m)! Таким образом, если принять множество всех литералов во всех дизъюнктах за N (n*m=N), то временная сложность алгоритма при равномерном весовом критерии есть O(N*N!). Временная сложность при логарифмическом весовом критерии. Здесь в основном происходят сравнения строковых величин – литералов, которые имеют одинаковую логарифмическую временную сложность (1). Следовательно, логарифмическая временная сложность всего алгоритма будет равняться равномерной временной сложности n*m*(n*m)! и она есть O(N*N!). Емкостная сложность при равномерном весовом критерии. Очевидно определяется размерами n*m массива, поэтому есть O(N). Емкостная сложность при логарифмическом весовом критерии. Определяется с одной стороны размером задействованных массивов и их элементов (примем за 1), а с другой – емкостями счетчиков: 6*N+2*n+m+2 Окончательно имеем O(N). Упражнения для практического занятия № 4

Тип работы:

Контрольная работа

Предмет:

Логика

Статус:

выполнено

Стоимость. Рублей:

90

Дата выполнения:

2014-12-20

Understand your user experience

I am text block. Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

Read More

remain responsive across devices

I am text block. Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

Read More

fall in love with our features

Real time stats

Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec mattis, pulvinar dapibus leo.

Multilingual & translatable

Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec mattis, pulvinar.

Less plugins needed

Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec mattis, pulvinar dapibus leo.

Amazingly responsive

Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec mattis, pulvinar dapibus leo.

Community builder

Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec mattis, pulvinar dapibus leo.

Easy to use interface

Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec mattis, pulvinar dapibus leo.

Выполним любую работу на заказ

У нас вы можете заказать уникальное решений этой задачи или любой другой

Adblock detector