Исправлены упражнения по временной сложности

Следующие исправленные упражнения относятся к анализу алгоритмов, в частности точности, полноте и расчету временной сложности.

расчет временной сложности

Упражнение 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-оператор
    конец для
конец, если

Каково время работы этого алгоритма при каждом из следующих наборов предположений? Обоснуйте свои ответы.

  1. ТВ(п) = О(п), ТБ(п) = О (п2) и тПРОТИВ(n) = O (log n).
  2. ТВ(п) = О (п2), ТБ(п) = О (п2) и тПРОТИВ(n) = O (log n).
  3. ТВ(п) = О (п2), ТБ(п) = О (п3) и тПРОТИВ(n) = O (log n).

Поскольку большие значения n определяют асимптотическое время выполнения, мы можем пренебречь частью if оператора if. Следовательно, во всех случаях время работы этого алгоритма равно O(TA(n) + nTC(n)).

  1. O (n журнал n)
  2. О (n²)
  3. О (n²)
Если у вас есть какие-либо сомнения, вы также можете использовать классическую формулу в случае ветвления 0 (max (T_branches)). В этом случае у нас было бы O(TA(n) + max(TC(n), nTC(n))).

Упражнение 6

Какова наихудшая сложность каждого из следующих фрагментов кода?

Две петли подряд:

  1. для (я = 0; я < N; я ++) {
  2. последовательность операторов}
  3. для (j = 0; j < M; j++) {
  4. последовательность операторов}

Как изменится сложность, если второй цикл перейдет к N вместо M?

Вложенный цикл, за которым следует невложенный цикл:

  1. для (я = 0; я < N; я ++) {
  2. для (j = 0; j < N; j++) {
  3. последовательность операторов
  4. }}
  5. для (к = 0; к < N; к++) {
  6. последовательность операторов}

Вложенный цикл, в котором количество выполнений внутреннего цикла зависит от значения индекса внешнего цикла:

  1. для (я = 0; я < N; я ++) {
  2. для (j = N; j > i; j–) {
  3. последовательность операторов
  4. }}
  1. Первая петля — 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).
  2. Первый набор вложенных циклов — O(N²), а второй — O(N). Это O(N²+N), что равно O(N²).
  3. Это очень похоже на наш предыдущий пример вложенного цикла, где количество итераций внутреннего цикла зависит от значения индекса внешнего цикла. Единственное отличие состоит в том, что в этом примере индекс внутреннего цикла ведет обратный отсчет от N до i+1. Всегда бывает так, что внутренний цикл выполняется N раз, затем N-1, затем N-2 и т. д., поэтому общее количество раз, когда самая внутренняя «последовательность операторов» выполняется, равно O (N²).

Упражнение 7

Дайте анализ времени выполнения (обозначение Big-Oh) для каждого из следующих 4 фрагментов программы. Обратите внимание, что время выполнения здесь соответствует тому, сколько раз выполняется операция sum++. sqrt — это функция, которая возвращает квадратный корень из заданного числа.

временная сложность коррекция сложности алгоритм завершения корректируемые упражнения

  1. Если выполнение программы (b) для n=100 занимает 10 мс, сколько времени потребуется для выполнения n=400?
  2. Если для запуска программы (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_RURU