14 - Сложность вычислений

1. Задан массив X[1..N]. Определите число операций сложения, которые выполняются при работе этой программы:
  S:=X[1]+X[N];
for k:=1 to N do
X[k]:=X[k]+X[k]+S;
Для обозначения операции умножения используйте символ *.
Ответ: 
2. Задан массив X[1..N]. Определите число операций умножения, которые выполняются при работе этой программы:
  S:=X[1]*X[N];
for k:=1 to N do begin
X[k]:=2*X[k]+S;
for i:=1 to 3 do
S:=S*2;
end;
Для обозначения операции умножения используйте символ *.
Ответ: 
3. Задан массив X[1..N]. Определите число операций сложения, которые выполняются при работе этой программы:
  S:=X[1]+X[N]+3;
for k:=1 to N do
for m:=1 to N do
X[k]:=X[k]+S;
Для обозначения операции умножения используйте символ *.
Ответ: 
4. Задан массив X[1..N]. Определите временную сложность алгоритма:
  S:=X[1]+X[N];
for k:=1 to N do
for m:=1 to 5 do
X[k]:=X[k]+S;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
5. Задан массив X[1..N]. Определите временную сложность алгоритма:
  S:=X[1]+X[N];
for k:=1 to N do
for m:=1 to k do
X[k]:=X[k]+X[m]+S;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
6. Задан массив X[1..N]. Определите временную сложность алгоритма:
  S:=X[1]+X[N];
for k:=1 to N do
for m:=1 to N do
for q:=1 to k do
X[k]:=X[k]+X[q]+S;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
7. Задан массив X[1..N]. Определите временную сложность алгоритма:
  function Rec(N: integer): integer;
begin
Rec:=0;
if N > 3 then
Rec:=Rec+Rec(N-1)+2*Rec(N-2);
end;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
8. Задан массив X[1..N]. Определите временную сложность алгоритма:
  S:=X[1]+X[N];
for k:=1 to N do
for m:=1 to 2*N*N do
X[k]:=X[k]+X[m]+S;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
9. Задан массив X[1..N]. Определите временную сложность алгоритма:
  L:=1; 
R:=N+1;
while L<R-1 do begin
c:=L+div(R-L,2)
if R < X[c] then R:=c
else L:=c;
end;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
10. Задан массив X[1..N]. Определите временную сложность алгоритма:
  k:=0;
for i:=1 to N do
if X[i] = R then begin
k:=i;
break;
end;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
11. Задан массив X[1..N]. Определите временную сложность алгоритма:
  for i:=1 to N-1 do
for j:=N-1 downto i do
if A[j]>A[j+1] then
Swap(A[j], A[j+1]);
O(log N)
O(N)
O(N2)
O(N3)
O(2N)