starsresearch

назад ***

1. Расположите функции в порядке увеличения скорости их асимптотического роста.

• $\sqrt{n}$ – 1
• $n{\ln{n}}$ – 2
• $9^{\log_{3}n}$ – 3
• $n^82^n$ – 4
• $e^n$ – 5

2. Найдите асимптотическую оценку скорости роста решений рекуррентного соотношения:

$T(n) = 7T(\frac{n}{6})+n\ln n$

• $\theta(n^{\log_{6}}7{\log_{2}n})$
• $\theta(n^{\log_{6}7})$
• $\theta(n)$
• $\theta(n{\ln{n}})$

3. Сколько сравнений в среднем сделает алгоритм двоичного поиска в массиве list при поиске значения присутствующего в массиве? Если потребуется, ответ округлить до сотых.

list = [1,2,3,4,5,6,7,8,9,10,11,12, 13, 14,15, 16,17, 18, 19,20,21,22,23,24,25,26]

• 4

4. Сколько сравнений в среднем сделает алгоритм интерполяционного поиска в массиве list при поиске значения присутствующего в массиве?

list = [1, 2, 6, 8, 9, 10, 13, 15, 19, 23, 25, 28, 30, 34, 39, 42, 45, 53, 58, 60]

• 2,45

5. Сколько инверсий в массиве list?

list = [1, 4, ..., 3n-2, 2, 5, ..., 3n-1, 3, 6, .., 3n]

Вычислите при n = 38

• 2109

6. Сколько сравнений сделает алгоритм Шелла со смещениями Пратта $(2^i3^j\le\frac{n}{2})$ при сортировки массивы list по возрастанию.

list = [6, 5, 7, 1, 3, 4, 2]

• 7

7. Вычислить количество сравнений выполняемых алгоритмом шейкерной сортировки при сортировке по возрастанию массива:

[9, 2, 12, 1, 4, 11, 10, 13, 7, 3, 19, 5, 20, 15, 6, 8, 14, 16, 18, 17]

(Первый проход слева направо. Если в проходе обменов нет, алгоритм прекращает работу.)

• 145

8. Вычислить количество сравнений выполняемых алгоритмом сортировки вставками при сортировке по возрастанию массива:

[19,17,15,13,11,9,7,5,3,1,20,18,16,14,12,10,8,6,4,2]

• 145

9. Вычислить количество сравнений выполняемых алгоритмом сортировки вставками при сортировке по возрастанию массива:

[18, 2, 12, 15, 4, 20, 10, 13, 7, 3, 19, 5, 11, 1, 6, 8, 14, 16, 9, 17]

• 81

10. Вычислить количество сравнений выполняемых алгоритмом сортировки Шелла. Значения смещений равны $h_s$, где $h_{s+1} = 2h_s +1$, $h_0 = 1$, причем $0 \le s < [\log2{N}]$ при сортировке по возрастанию массива:

[9, 2, 12, 1, 4, 11, 10, 13, 7, 3, 19, 5, 20, 15, 6, 8, 14, 16, 18, 17]

• 27