Паскаль: 17 - Сложность алгоритмов

1. Задан массив X[1..N]. Определите число операций сложения, которые выполняются при работе этой программы:
  S:=X[1]+X[N];
for k:=1 to N do begin
X[k]:=X[k]+X[k]+S
end;
Для обозначения операции умножения используйте символ *.
Ответ: 
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. Количество операций при выполнении некоторого алгоритма равно
  T(N) = 5*N2 + 3*N + 1
Определите наиболее точную оценку временной сложности алгоритма.
O(1)
O(N)
O(N2)
O(N3)
O(2N)
5. Количество операций при выполнении некоторого алгоритма равно
  T(N) = N3 - 3*N2 + N
Определите наиболее точную оценку временной сложности алгоритма.
O(1)
O(N)
O(N2)
O(N3)
O(2N)
6. Количество операций при выполнении двух алгоритмов для массива размером N таково:
  T1(N) = N2 - N - 10
T2(N) = 4N + 40
Определите размер массива N, для которого время выполнения обоих алгоритмов одинаково.
Ответ: 
7. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
for k:=1 to N do
X[k]:=X[k]+S;
O(1)
O(N)
O(N2)
O(N3)
O(2N)
8. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
for k:=1 to N do begin
for m:=1 to 5 do begin
X[k]:=X[k]+S
end
end;
O(1)
O(N)
O(N2)
O(N3)
O(2N)
9. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
for k:=1 to N do
for m:=1 to N do
for q:=1 to N do
X[k]:=X[k]+X[q]+S;
O(1)
O(N)
O(N2)
O(N3)
O(2N)
10. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
for k:=1 to N do
for m:=2 to 2*N*N do begin
X[k]:=X[k]+X[m]+S
end;
O(1)
O(N)
O(N2)
O(N3)
O(2N)
11. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  k:=0;
for i:=1 to N do
if X[i] = R then begin
k:=i;
break
end;
O(1)
O(N)
O(N2)
O(N3)
O(2N)