|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 17 Feb 2003 18:40:45
To : Alexy Medveschek
Subject : Quick Sort
--------------------------------------------------------------------------------
17 Feb 03 17:21, you wrote to me:
SS>>>>> Доказательство говорит, что быстрее, чем O(NlogN) не бывает.
AM> ^^^^^^^^^^^^^^
AM> Прошу прощения, что влез в разговор (тем более так "вовремя" ;),
AM> но на моей памяти не встречалось этого доказательства, и даже напротив
что значит, "и даже напротив" ?
ты хоть сам понял, что сказал ? %)
AM> говорилось о невозможности доказать, что не существует алгоритмов
AM> порядка приближенного к N.
Доказательство, что алгоритм, основанный на сравнении между элементами,
невозможно сделать быстрее, чем O(NlogN) вообще-то включает как частный
случай и факт, что не существует алгоритмов, основанных на сравнении
между элементами, порядка приближенного к N.
AM> Если таковое и правда есть, то где можно посмотреть (доки,
AM> URL...).
Кнут, Кормен, лекции по алгоритмам в любом ВУЗе.
E-mail: gate@fidonet.org.il
Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
Bye !
Stanislav (AKA Night's Man) [Team Technion]
---
* Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
