Всем привет! Купил Кормена и пытаюсь разбираться, но так как

Question

Всем привет! Купил Кормена и пытаюсь разбираться, но так как

в математике не профи, возникли проблемы. Кто-нибудь может, пожалуйста, помочь с решением задачи (всеми четырьмя её пунктами) с объяснением шагов?

#proalgoritms #russian

0

13.11.2021

8 ответов

15 просмотров

Oppo Автор вопроса

Constantine Drozdov
Не очень понятно, в чём конкретно у вас возникает ...

Если говорить о пункте б, то здесь, честно говоря, тоже мало понятного. В примере про сортировку слиянием записано рекуррентное соотношение (на рисунке), в котором за слияние "отвечает" слагаемое THETA(n). Но в случае разбиения массива на m частей, какое слагаемое будет? THETA(m)?

0

13.11.2021

Oppo Автор вопроса

Хорошо, сейчас перечитаю. У меня ещё другой вопрос есть. Как определить (сформулировать?) инвариант цикла? Это относится к задаче "2.2 Корректность пузырьковой сортировки" (стр.63 у меня). Я расписал эту сортировку на примере массива [5,2,4,6,1,3] пошагово, но не могу понять (увидеть) какое условие соблюдается для каждой итерации перед началом и в конце. Или тут тоже просто что-то перечитать нужно?)

0

13.11.2021

Constantine Drozdov

Oppo
Хорошо, сейчас перечитаю. У меня ещё другой вопрос...

Там будет что-то про сортированность какого-то фрагмента массива

0

13.11.2021

Oppo Автор вопроса

Constantine Drozdov
Там будет что-то про сортированность какого-то фра...

Хоть убей, но не вижу какого-либо условия, которое выполнялось бы в начале и конце каждой итерации цикла! Может, я скину фото, где пошагово "прошёлся", а вы посмотрите? Если вам не трудно, конечно

0

13.11.2021

evgeniy