Substitution method

Переклад книжки Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein "Introduction to Algorithms". Обговорення, термінологія.
Відповісти
sasha1024
Повідомлень: 65
З нами з: Вів січня 19, 2016 4:42 pm

Substitution method

Повідомлення sasha1024 »

  • метод підстановок,
  • метод підстановки?
pasichna
Повідомлень: 46
З нами з: Чет грудня 12, 2013 8:33 pm

Re: Substitution method

Повідомлення pasichna »

Множинна форма „метод підстановок“ правильна, бо при розв'язуванні цим методом здійснюється не одна підстановка, а цілий ряд послідовно крок за кроком, поки не дійдемо до базового значення T(1), хоча починаємо переважно від T(n). На кожному кроці підстановки зменшується на одиницю (чи на більше) найбільше значення змінної n у правій частині рекурентного співвідношення (n -> n-1-> n-2-> n-3->…->1).
sasha1024
Повідомлень: 65
З нами з: Вів січня 19, 2016 4:42 pm

Re: Substitution method

Повідомлення sasha1024 »

Я теж так думав (і навіть звучить так краще).
Але отут (Ваше посилання) — «метод підстановки».
Тому й вирішив перепитати (дякую).
pasichna
Повідомлень: 46
З нами з: Чет грудня 12, 2013 8:33 pm

Re: Substitution method

Повідомлення pasichna »

Мусив заглянути в англійський оригінал тої книжки. Автори по іншому подають цей метод, ніж я звик. В їхньому аналізі використовується таки дійсно одна підстановка, бо вони припускають представлення розв'язку у вигляді загальної формули з кількома параметрами, яку й підставляють у рекурентне співвідношеня для відшукання параметрів.

Хоча у книжці Boxer, Laurence, and Russ Miller. Algorithms Sequential and Parallel : A Unified Approach, Course Technology, 2005 той метод інакше описаний - саме так я писав у попередній відповіді.
Треба дотримуватися тлумачення авторів.
Відповісти

Повернутись до “Переклад "Introduction to Algorithms"”