Информатика, сложность алгоритмов, кумир 1. Задан массив X[1..N]. Определите число операций сложения, которые выполняются при работе этой программы:
S:=X[1]+X[N]
нц для k от 1 до N
X[k]:=X[k]+X[k]+S
кц
Для обозначения операции умножения используйте символ *.
ответ:
введите строку
2. Задан массив X[1..N]. Определите число операций умножения, которые выполняются при работе этой программы:
S:=X[1]*X[N]
нц для k от 1 до N
X[k]:=2*X[k]+S
нц для i от 1 до 3
S:=S*2
кц
кц
Для обозначения операции умножения используйте символ *.
ответ:
введите строку
3. Задан массив X[1..N]. Определите число операций сложения, которые выполняются при работе этой программы:
S:=X[1]+X[N]+3
нц для k от 1 до N
нц для m от 1 до N
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]
нц для k от 1 до N
X[k]:=X[k]+S
кц
O(1)
O(N)
O(N2)
O(N3)
O(2N)
8. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
S:=X[1]+X[N]
нц для k от 1 до N
нц для m от 1 до 5
X[k]:=X[k]+S
все
все
O(1)
O(N)
O(N2)
O(N3)
O(2N)
9. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
S:=X[1]+X[N]
нц для k от 1 до N
нц для m от 1 до N
нц для q от 1 до N
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]
нц для k от 1 до N
нц для m от 1 до 2*N*N
X[k]:=X[k]+X[m]+S
все
все
O(1)
O(N)
O(N2)
O(N3)
O(2N)
11. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
k:=0
нц для i от 1 до N
если X[i] = R то
k:=i
выход
все
кц
O(1)
O(N)
O(N2)
O(N3)
O(2N)
Объяснение: сори