Сложность алгоритмов

Задан массив X[0..N-1]. Определите число операций сложения, которые выполняются при работе этой программы:

S=X[0]+X[N-1];

for(k=0;

k<N;

k++) X[k]+=X[k]+S;

(a)  

Задан массив X[0..N-1]. Определите число операций умножения, которые выполняются при работе этой программы:

S=X[0]*X[N-1];

for(k=0; k<N; k++)

{ X[k]=2*X[k]+S;

for(i=0; i<3; i++)

S=S*2; }

Для обозначения операции умножения используйте символ *.

(a)  

Задан массив X[0..N-1]. Определите число операций сложения, которые выполняются при работе этой программы:

S=X[1]+X[N-1]+3;

for(k=0; k<N; k++)

for(m=0; m<N; m++)

X[k]+=S;

Для обозначения операции умножения используйте символ *.

(a)  

Количество операций при выполнении некоторого алгоритма равно

T(N) = 5*N² + 3*N + 1

Определите наиболее точную оценку временной сложности алгоритма.

• O(1)

• O(N)

• O(N²)

• O(N³)

• O(2^N)

Количество операций при выполнении некоторого алгоритма равно

T(N) = N³ - 3*N² + N

Определите наиболее точную оценку временной сложности алгоритма.

• O(1)

• O(N)

• O(N²)

• O(N³)

• O(2^N)

Количество операций при выполнении двух алгоритмов для массива размером N таково:

T₁(N) = N² - N - 10 T₂(N) = 4N + 40

Определите размер массива N, для которого время выполнения обоих алгоритмов одинаково.

(a)  

Задан массив X[0..N-1]. Определите наиболее точную оценку временной сложности алгоритма:

S=X[0]+X[N-1];

for(k=0; k<N; k++)

X[k]+=S;

• O(1)

• O(N)

• O(N²)

• O(N³)

• O(2^N)

Задан массив X[0..N-1]. Определите наиболее точную оценку временной сложности алгоритма:

S=X[0]+X[N-1];

for(k=0; k<N; k++)

for(m=0; m<N; m++)

X[k]+=S;

• O(1)

• O(N)

• O(N²)

• O(N³)

• O(2^N)

Задан массив X[0..N-1]. Определите наиболее точную оценку временной сложности алгоритма:

S=X[0]+X[N-1];

for(k=0; k<N; k++)

for(m=0; m<N; m++)

for(q=0; q<N; q++)

X[k]+=X[q]+S

• O(1)

• O(N)

• O(N²)

• O(N³)

• O(2^N)

Задан массив X[0..N-1]. Определите наиболее точную оценку временной сложности алгоритма:

S=X[0]+X[N-1];

for(k=0; k<N; k++)

for(m=0; m<2*N*N; m++)

X[k]+=X[m]+S;

• O(1)

• O(N)

• O(N²)

• O(N³)

• O(2^N)