Упражнение 1
Определим временную сложность алгоритма Check:
Перед вычислением сложности необходимо проверить, завершается ли алгоритм. Элементы массива являются целыми числами, поэтому могут превышать значение 9, что означает, что tab[value-1] выпадает из размера массива. Следовательно, алгоритм нежизнеспособен и бесполезен для дальнейшего анализа.
Упражнение 2
Проанализируйте сложность алгоритма. Написать еще алгоритм который делает то же самое, что и алгоритм, но со строго лучшей асимптотической временной сложностью.
Алгоритм действительно сложен для понимания. Самый простой способ — проверить его работу с небольшим вектором, например <3, 5, 4, 4, 5, 7>. Я позволю вам проверить шаг за шагом на бумаге.
В цикле, когда два ящика идентичны, мы увеличиваем значение c. Учитывая последовательное содержимое в цикле, i остается стабильным, в то время как j развивается. Таким образом, мы подсчитываем количество вхождений в таблицу значения поля i. Вторая ветвь дает условие, когда j достигает своего рода размера вектора. В этом случае проверяется, что количество вхождений значения поля i превышает последнее число, записанное в m. Затем мы увеличиваем i и помещаем j в тот же квадрат.
Это не меняет операции нахождения количества вхождений каждого поля, потому что если значение было раньше, то оно уже полностью подсчитано. Именно запуск i и j в одном и том же месте приводит к меньшему количеству вычислений.
Если мы возобновим операцию, i и j окажутся в одном ящике. j увеличивается до конца массива. Затем я перемещаюсь вперед на одну позицию, а J перемещаюсь в то же место. Таким образом, количество итераций равно сумме n (размера массива) и 1, т.е. n(n-1)/2. Обе ветви имеют одинаковую сложность в 0(1), поэтому сложность алгоритма равна O(n²).
Для упрощения достаточно провести алгоритм в два этапа. Сначала сортируем таблицу (можно за O(n log(n)). Затем читаем таблицу по двум полям tab[i] и tab[i+1]. Пока значения равны, увеличиваем счетчик c. Если он отличается, мы смотрим, является ли c>m предложенным алгоритмом. Следовательно, сложность составляет O (n log (n) + n) или O (n log (n)).
Упражнение 3
Заполните две таблицы ниже:
Упражнение 4
Каково (асимптотическое) время работы каждого из следующих алгоритмов в зависимости от n? Обоснуйте свои ответы.
имеет)
для i = 1 до n сделать
для j = 1 до 2n + 1 сделать
print("Привет мир)
конец для
конец для
б)
для i = от 1 до 10 сделать
для j = 1 до n сделать
печать («Привет, мир»)
конец для
конец для
против)
для i = 1 до n сделать
для j = i to n сделать
печать («Привет, мир»)
конец для
конец для
г)
для i = 1 до n сделать
для j = 1 до 2 ∗ i + 1 сделать
печать («Привет, мир»)
конец для
конец для
д)
для i = 1 до n ∗ n сделать
для j = 1 я делаю
печать («Привет, мир»)
конец для
конец для
е)
для (i = от 0 до m) сделать
← 1
в то время как (t < m) делать
print("Привет, мир")
т ← т * 2
конец, пока
конец для
а) О(n²). Здесь первый цикл выполняет (n-1) итераций, а второй цикл — 2n итераций, так что всего (n-1)*2n.
Что ж). Здесь первый цикл делает 10 итераций, а второй цикл — n итераций, так что всего 10n. Внимание, согласно определенному расчету, это будет 9 итераций, за которыми следуют n-1 итерации. К счастью, в Обозначение Ландау это ничего не меняет, поэтому нет необходимости придираться к количеству итераций!
в) О(n²). Очень классический, каждый цикл делает n-1 итераций.
г) О(n²). Первая петля классическая. Второй идет от 1 до 2i+1, поэтому если мы сделаем несколько примеров: 3, 5, 7, …, 2n+1 (здесь мы запускаем два цикла одновременно). Таким образом, у нас есть сумма первых n нечетных членов, следовательно, квадратичная.
Также возможно рассчитать сложность путем умножения сложности каждого из циклов. Первый цикл стремится к n итерациям, когда n велико; второй цикл стремится к n итерациям, когда n велико. Итак, у нас есть сложность O(n*n)=O(n²).
Будьте осторожны, чтобы проверить количество итераций, когда n велико, оно не всегда будет в O (n)!
д) О(п^4). Отражение такое же, как для алгоритма d. Здесь у нас есть первые n членов в квадрате.
е) O(m log(m)). Для первого цикла все нормально, со вторым будет проблема. Здесь значение t удваивается на каждой итерации, и цикл останавливается, когда t превышает значение m. Пусть k - количество выполненных итераций. Мы останавливаемся, когда 2^к > m, поэтому, когда k > log (m). Отсюда сложность.
Упражнение 5
Пусть ТВ(н), ТБ(п) и ТПРОТИВ(n) время выполнения алгоритмов A, B и C соответственно.
Заявление А
если (n < 100), то
Заявление Б
еще
для (j = 1 до n) сделать
C-оператор
конец для
конец, если
Каково время работы этого алгоритма при каждом из следующих наборов предположений? Обоснуйте свои ответы.
- ТВ(п) = О(п), ТБ(п) = О (п2) и тПРОТИВ(n) = O (log n).
- ТВ(п) = О (п2), ТБ(п) = О (п2) и тПРОТИВ(n) = O (log n).
- ТВ(п) = О (п2), ТБ(п) = О (п3) и тПРОТИВ(n) = O (log n).
Поскольку большие значения n определяют асимптотическое время выполнения, мы можем пренебречь частью if оператора if. Следовательно, во всех случаях время работы этого алгоритма равно O(TA(n) + nTC(n)).
- O (n журнал n)
- О (n²)
- О (n²)
Упражнение 6
Какова наихудшая сложность каждого из следующих фрагментов кода?
Две петли подряд:
- для (я = 0; я < N; я ++) {
- последовательность операторов}
- для (j = 0; j < M; j++) {
- последовательность операторов}
Как изменится сложность, если второй цикл перейдет к N вместо M?
Вложенный цикл, за которым следует невложенный цикл:
- для (я = 0; я < N; я ++) {
- для (j = 0; j < N; j++) {
- последовательность операторов
- }}
- для (к = 0; к < N; к++) {
- последовательность операторов}
Вложенный цикл, в котором количество выполнений внутреннего цикла зависит от значения индекса внешнего цикла:
- для (я = 0; я < N; я ++) {
- для (j = N; j > i; j–) {
- последовательность операторов
- }}
- Первая петля — O(N), вторая петля — O(M). Поскольку вы не знаете, что больше, вы говорите, что это O(N+M). Его также можно записать O(max(N,M)). В случае, когда второй цикл идет к N вместо M, сложность равна O(N). Вы можете увидеть это из любого из приведенных выше выражений. O(N+M) становится O(2N), а когда вы удаляете константу, это O(N). O (max (N, M)) становится O (max (N, N)), что равно O (N).
- Первый набор вложенных циклов — O(N²), а второй — O(N). Это O(N²+N), что равно O(N²).
- Это очень похоже на наш предыдущий пример вложенного цикла, где количество итераций внутреннего цикла зависит от значения индекса внешнего цикла. Единственное отличие состоит в том, что в этом примере индекс внутреннего цикла ведет обратный отсчет от N до i+1. Всегда бывает так, что внутренний цикл выполняется N раз, затем N-1, затем N-2 и т. д., поэтому общее количество раз, когда самая внутренняя «последовательность операторов» выполняется, равно O (N²).
Упражнение 7
Дайте анализ времени выполнения (обозначение Big-Oh) для каждого из следующих 4 фрагментов программы. Обратите внимание, что время выполнения здесь соответствует тому, сколько раз выполняется операция sum++. sqrt — это функция, которая возвращает квадратный корень из заданного числа.
- Если выполнение программы (b) для n=100 занимает 10 мс, сколько времени потребуется для выполнения n=400?
- Если для запуска программы (a) для n=100 требуется 10 мс, задачу какого размера можно решить за 40 мс?
A находится в O (sqrt (n)) это последовательная последовательность циклов, у нас есть 0 (sqrt (n)/2 + sqrt (n)/4 + sqrt (n)/4 +8)
Б не кончается, второй цикл плохо прописан! При правильном написании цикла у нас было бы три взаимозависимых цикла, ограниченных точками 0(sqrt(n)), 0(1) и O(1) — от i до i+8; от d до d+8, что составляет всего 8 итераций. Что равно 0 (кварт (n)).
c находится в O (n ^ 5). Три вложенных цикла соответствующей сложности 0(n), 0(n²), 0(n²), следовательно, 0(n*n²*n²).
d имеет условие ветвления, которое недопустимо, поскольку оно не возвращает логическое значение, алгоритм не завершается, поэтому нет необходимости вычислять сложность.
С векторным произведением: sqrt(100)=x и y=10 мс; sqrt(400)=2x занимает 20 мс
Через 40 мс n=1600.
RU 
FR 
EN 
ES