Сложность времени в алгоритмах Divide and Conquer

Не могли бы вы помочь мне в понимании алгоритма Time Complexity для Divide и Conquer.Сложность времени в алгоритмах Divide and Conquer

Давайте рассмотрим пример этого. http://www.geeksforgeeks.org/archives/4583 Способ 2: Он дал T (n) = 3/2n -2, и я не понимаю, почему?

Прошу прощения, если бы я дал вам дополнительную страницу, чтобы открыть ее, но я действительно хочу понять atleast на хорошем высоком уровне, так что я могу найти сложность таких алгоритмов самостоятельно, вы отвечаете высоко оценили.

источник

2011-12-21 Aj Gauravdeep

Чтобы объяснить это, нам действительно нужно знать ваш текущий уровень понимания. Например, ваша сила в анализе рекурсивного алгоритма и сложности в целом. Я предлагаю вам попытаться найти некоторые интерактивные слайды. –

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

Как вычислить временную сложность: Предположим, что время, затраченное на ваш алгоритм, - T (n). Обратите внимание, что затраченное время является функцией размера проблемы, то есть n.

Теперь обратите внимание, что вы делаете. Вы разбиваете проблемы, скажем, на k частей каждого размера n/k (они могут быть не равными по размеру, и в этом случае вам придется добавить время, затраченное ими отдельно). Теперь вы решите эти части. Время, затрачиваемое каждой частью, будет T (n/k), так как размер проблемы теперь уменьшается до n/k. И вы решаете их. Итак, время k * T (n/k).

После решения этих небольших проблем вы объедините их решения. Это займет некоторое время. И это время снова будет функцией вашего размера проблемы. (Он также может быть постоянным). Пусть это время O (f (n)).

Таким образом, общее время, затраченное на ваш алгоритм будет: Т (п) = (А * Т (п/к)) + O (F (N))

Вы получили рекуррентное соотношение теперь вы можете решить получить T (n).

источник

2011-12-21 08:51:39 Divya

Не стесняйтесь спрашивать о новых предложениях. – Divya

Спасибо, Дивья. Я, я пошел на этот веб-сайт и, похоже, достиг своего потенциала и, таким образом, не смог выполнить услугу. На самом деле то, что вы объяснили, я уже знал до этой части, но, это моя математика, которая меня сбивает с толку. Но лемме дотянуться до моих старых книг в колледже и попытаться понять. Большое спасибо за ваше время. –

Если вы ищете «как решить рекуррентные отношения», вы можете проверить эту ссылку http://www.cs.ucr.edu/~jiang/cs141/recur-tut.txt Это быстрый учебник, который охватывает различные методы решения рекуррентных отношений. Рад был помочь! :) @Leoheart – Divya

В этой связи указывают:

T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2 
    T(2) = 1 
    T(1) = 0

для T(2), это база с одной сравнения перед возвращением. для T(1) это база без какого-либо сравнения.
Для T(n): Вы рекурсивный вызов метода для двух половин массива и сравнить два (мин, макс) кортежи, чтобы найти реальную мин и макс, который дает вам выше T(n) уравнение

If n is a power of 2, then we can write T(n) as: 

    T(n) = 2T(n/2) + 2

Этот хорошо объясняет сам.

T(n) = 3/2n -2

Здесь, вы решить с индукцией:
базовый случай: при п = 2: T(2) = 1 = (3/2)*2 -2
Мы предполагаем, T(k) = (3/2)k - 2 для каждого k < n
T(n) = 2T(n/2) + 2 = (*) 2*((3/2*(n/2)) -2) + 2 = 3*(n/2) -4 + 2 = (3/2)*n -2
(*) индуктивного предположения, верно, потому что

Поскольку мы доказали правильность индукции, мы можем заключить: T(n) = (3/2)n - 2

источник

2011-12-21 09:01:58 amit

Привет, как мы можем сделать это доказательство с k + 1 членом, который используется в доказательстве по индукции? – RichArt

Сложность времени в алгоритмах Divide and Conquer

ответ

Смежные вопросы