Информатика, сложность алгоритмов, кумир 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)

Объяснение: сори

1. Чтобы определить число операций сложения, нужно посмотреть, сколько раз выполняется операция сложения X[k]+X[k]+S. В данном случае эта операция выполняется внутри цикла для каждого k от 1 до N, то есть N раз. Также есть операция сложения S:=X[1]+X[N], которая выполняется один раз перед началом цикла. Итого, общее число операций сложения будет равно N+1.
Ответ: N+1 операций сложения.

2. Чтобы определить число операций умножения, нужно посмотреть, сколько раз выполняется операция умножения X[k]:=2*X[k]+S. В данном случае эта операция выполняется внутри цикла для каждого k от 1 до N, то есть N раз. Также есть операция умножения S:=S*2, которая выполняется внутри вложенного цикла для каждого i от 1 до 3, то есть 3 раза перед каждым внешним циклом. Итого, общее число операций умножения будет равно 3*N.
Ответ: 3*N операций умножения.

3. Чтобы определить число операций сложения, нужно посмотреть, сколько раз выполняется операция сложения X[k]:=X[k]+S. В данном случае эта операция выполняется внутри двух циклов: цикла для k от 1 до N и цикла для m от 1 до N. Оба цикла выполняются N раз, поэтому общее число операций сложения будет равно N*N.
Ответ: N*N операций сложения.

4. В данном случае имеется алгоритм с постоянной временной сложностью, так как количество операций не зависит от размера входных данных N. В выражении T(N) = 5*N^2 + 3*N + 1, коэффициенты при N^2 и N являются константами, поэтому они не влияют на рост временной сложности алгоритма с увеличением N. Основным параметром, определяющим время выполнения, является константа 1, которая означает выполнение одной операции за постоянное время.
Ответ: O(1).

5. В данном случае имеется алгоритм с временной сложностью O(N^3), так как наивысший степенной член N^3 определяет рост временной сложности алгоритма при увеличении размера входных данных N. Коэффициенты при N^2 и N могут влиять на рост временной сложности, но их эффект пренебрежимо мал по сравнению с N^3.
Ответ: O(N^3).

6. Чтобы определить размер массива N, при котором время выполнения обоих алгоритмов одинаково, нужно приравнять выражения T1(N) и T2(N) и решить полученное уравнение.
Выражение T1(N) = N^2 - N - 10.
Выражение T2(N) = 4N + 40.
Приравнивая оба выражения, получим уравнение:
N^2 - N - 10 = 4N + 40.
Путем решения этого уравнения можно найти значение N.
Ответ: введите число, которое найдется путем решения уравнения N^2 - N - 10 = 4N + 40.

7. Чтобы определить наиболее точную оценку временной сложности алгоритма, нужно посмотреть, сколько раз выполняется операция X[k]:=X[k]+S. В данном случае эта операция выполняется внутри цикла для каждого k от 1 до N, то есть N раз. Также есть операция сложения S:=X[1]+X[N], которая выполняется один раз перед началом цикла. Итого, общее число операций сложения будет равно N+1.
Ответ: O(N) временная сложность алгоритма.

8. Чтобы определить наиболее точную оценку временной сложности алгоритма, нужно посмотреть, сколько раз выполняется операция X[k]:=X[k]+S. В данном случае эта операция выполняется внутри двух циклов: цикла для k от 1 до N и цикла для m от 1 до 5. Оба цикла выполняются N и 5 раз соответственно. Также есть операция сложения S:=X[1]+X[N], которая выполняется один раз перед началом циклов. Итого, общее число операций сложения будет равно (5N+1)+1.
Ответ: O(N) временная сложность алгоритма.

9. Чтобы определить наиболее точную оценку временной сложности алгоритма, нужно посмотреть, сколько раз выполняется операция X[k]:=X[k]+X[q]+S. В данном случае эта операция выполняется внутри трех циклов: цикла для k от 1 до N, цикла для m от 1 до N и цикла для q от 1 до N. Все три цикла выполняются N раз. Также есть операция сложения S:=X[1]+X[N], которая выполняется один раз перед началом циклов. Итого, общее число операций сложения будет равно N*N*N.
Ответ: O(N^3) временная сложность алгоритма.

10. Чтобы определить наиболее точную оценку временной сложности алгоритма, нужно посмотреть, сколько раз выполняется операция X[k]:=X[k]+X[m]+S. В данном случае эта операция выполняется внутри двух циклов: цикла для k от 1 до N и цикла для m от 1 до 2N^2. Первый цикл выполняется N раз, а второй цикл выполняется 2N^2 раз. Также есть операция сложения S:=X[1]+X[N], которая выполняется один раз перед началом циклов. Итого, общее число операций сложения будет равно (2N^2+N)+1.
Ответ: O(N^2) временная сложность алгоритма.

11. В данном случае имеется алгоритм с временной сложностью O(N), так как наивысший степенной член N определяет рост временной сложности алгоритма при увеличении размера входных данных N. Коэффициент при N может влиять на рост временной сложности, но его эффект пренебрежимо мал по сравнению с N.
Ответ: O(N) временная сложность алгоритма.