Не могу понять CLRS Проблема 4-2, случай 2

Вопрос:

4-2 Затраты на передачу параметров

На протяжении всей этой книги мы предполагаем, что передача параметров во время вызовов процедур занимает постоянное время, даже если передается массив из N элементов. Это предположение справедливо в большинстве систем, поскольку передается указатель на массив, а не сам массив. Эта проблема исследует последствия трех стратегий передачи параметров:

  1. Массив передается по указателю. Тета времени(1)

<сильный>2. Массив передается путем копирования. Время Theta(N), где N — размер массива.

  1. Массив передается путем копирования только того поддиапазона, к которому может получить доступ вызываемая процедура. Время Theta(q-p+1), если передан подмассив A[p..q].

а. Рассмотрим алгоритм рекурсивного бинарного поиска для нахождения числа в отсортированном массиве (см. упражнение 2.3-5). Дайте повторения для наихудшего времени выполнения бинарного поиска, когда массивы передаются с использованием каждого из трех вышеперечисленных методов, и дайте хорошие верхние границы для решений повторений. Пусть N — размер исходной задачи, а n — размер подзадачи.

б. Повторите часть (a) для алгоритма MERGE-SORT из раздела 2.3.1.

У меня проблемы с пониманием того, как решить повторение случая 2, когда массивы передаются путем копирования для обоих алгоритмов.

Возьмем, к примеру, алгоритм бинарного поиска из случая 2. Большинство ответов дают следующее число: T(n)=T(n / 2)+Theta(N). У меня нет проблем с этим.

Вот ответ, который я нашел в Интернете, который выглядит правильно:

T(n)

= T(n/2) + cN

= 2cN + T(n/4)

= 3cN + T(n/8)

= Sigma (i = 0 до lgn - 1) (2 ^ i cN / (2 ^ i))

= cNlgn

= Тета (nlgn)

Мне трудно понять, как вторая последняя строка может привести к ответу последней строки. Почему бы не представить это в тета (Nlgn)? И как N может стать n в тета-обозначении?

N и n кажутся чем-то связанным. У меня проблемы с пониманием их связи и того, как это применяется в решении.


arrays performance algorithm clrs
person Xazy    schedule 14.08.2019    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Кажется, что N представляет полную длину массива, а n - текущий размер фрагмента.

Но формулы действительно используют только начальное значение, когда вы начинаете с полной длины n=N - например, посмотрите на T(n/4) вместо T(N/4), поэтому n===N везде.

В этом случае вы можете заменить n на N.

person MBo    schedule 14.08.2019

arrow_upward
0
arrow_downward

Мой ответ будет не очень теоретическим, но, возможно, этот «более эмпирический» подход поможет вам разобраться. Также проверьте Основную теорему (анализ алгоритмов), чтобы упростить анализ сложности рекурсивных алгоритмов.

Давайте сначала решим бинарный поиск:

  1. По указателю

    O(logN) - действует как итеративный бинарный поиск, будет logN вызовов, каждый из которых имеет O(1) сложность

  2. Копируем весь массив

    O(NlogN) - так как на каждый из logN вызовов функции мы копируем N элементов

  3. Копирование только доступного подмассива

    O(N) - это не так очевидно, но легко увидеть, что скопированные подмассивы будут иметь длину, N, N/2, N/4, N/8 .... и суммируя все эти члены, будут 2*N

Теперь об алгоритме сортировки слиянием:

  1. O(NlogN) - тот же метод, что и для a3, итерируемые подмассивы будут иметь длины N, (N/2, N/2), (N/4, N/4, N/4, N/4)...

  2. O(N^2) — делаем 2*N вызовов функции сортировки и каждый имеет сложность O(N) для копирования всего массива

  3. O(NlogN) — копировать будем только те подмассивы, по которым будем перебирать, поэтому сложность будет как в b1

person Razvan Turtu    schedule 14.08.2019