Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Алгоритм
|
|||
|---|---|---|---|
|
#18+
softwarer k-nikeИнтересно какие там еще данные требуются кроме самого массива? Которые "или файл" и "очень большой". Данные очень большого файла запросто могут не влезть в память. Хотите сказать для сортировки массива "или файл" или "очень большой" не важно? Я далеко не спец, но у меня очень большие сомнения по этому поводу. К тому же не обязательно читать файл целиком в обоих случаях. Еще про сортировку массива почитал тут , конкретная таблица тут . В худшем случае сложность сортировки массива О(N 2 ), т.е. такая же!!! А в среднем О(N*log2(N)). Остается посчитать среднюю сложность нелюбимого вами метода для полного понимания происходящего. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.09.2006, 14:53 |
|
||
|
Алгоритм
|
|||
|---|---|---|---|
|
#18+
k-nike2Хотите сказать для сортировки массива "или файл" или "очень большой" не важно? Смотря какой алгоритм. Скажем, для той же битовой карты - не важно. Популярность quicksort во многом обусловлена тем, что алгоритм отлично подходит для систем с виртуальной памятью. k-nike2К тому же не обязательно читать файл целиком в обоих случаях. Это не важно. Если читать файл целиком, сложность чтения O(N). Если требуется прочитать в среднем пол-файла, сложность чтения опять-таки O(N). И если не иметь данных о внутренней структуре файла, эту оценку улучшить не удастся. k-nike2В худшем случае сложность сортировки массива О(N 2 ), т.е. такая же!!! Да, выборка из трех алгоритмов позволяет сделать такой вывод. Для битовой карты в худшем случае сложность O(N). Такая же? k-nike2Остается посчитать среднюю сложность нелюбимого вами метода для полного понимания происходящего. Что ж, считайте. Вы двигаетесь в правильном направлении. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.09.2006, 20:28 |
|
||
|
Алгоритм
|
|||
|---|---|---|---|
|
#18+
Напоминаю с чего все началось: softwarer k-nikeНе могу написать формулу сложности алгоритма, но по-моему вариант когда: Код: plaintext 1. 2. 3. "По-моему" - вещь хорошая, но ей хорошо было бы быть верной или хотя бы хоть чем-нибудь подкрепленной. Я свои слова, как мне кажется, подкрепил. А про битовую карту я ничего не говорил и ни с чем ее не сравнивал. Или вы хотите сказать, что битовая карта и есть сортировка? Тогда я, конечно, не прав, но я имел ввиду обычную сортировку массива, типа, пузырьковой. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.09.2006, 20:47 |
|
||
|
Алгоритм
|
|||
|---|---|---|---|
|
#18+
k-nike2Напоминаю с чего все началось: Я помню. Это по сути пузырек, сложность O(N 2 ). k-nike2Я свои слова, как мне кажется, подкрепил. Чем? Вы назвали три алгоритма, у которых сложность в наихудшем случае такая же, какая у Вас в наилучшем. У одного из них такая же сложность в среднем случае, из-за чего его используют только очень ленивые и глупые студенты (глупые - потому что не способны списать откуда-нибудь более удачную реализацию). k-nike2Или вы хотите сказать, что битовая карта и есть сортировка? Битовая карта в принципе является алгоритмом сортировки. В случае конкретной задачи сортировка нам неинтересна, важен факт наличия дублей, который определяется аналогичным способом со сложностью O(N). k-nike2Тогда я, конечно, не прав, но я имел ввиду обычную сортировку массива, типа, пузырьковой. И? quicksort даст N log N. radix sort даст N. То и другое является "обычными сортировками". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.09.2006, 20:58 |
|
||
|
Алгоритм
|
|||
|---|---|---|---|
|
#18+
softwarerВы назвали три алгоритма, у которых сложность в наихудшем случае такая же, какая у Вас в наилучшем. Я смотрю мы все о разном. Я-то с дуру под сложность скорость подразумеваю, но как выяснилось скорость от сложности мало зависит (+/- бесконечность). см. ссылку вышеОсновным недостатком O-функций является их черезмерная грубость. Если алгоритм А выполняет некоторую задачу за 0.001*N с, в то время как для ее же решения с помощью алгоритма В требуется 1000*N с, то В в миллион раз быстрее, чем А. Тем не менее А и В имеют одну и ту же временную сложность O(N). К тому же, здесь уже говорилось, в том числе и вами, что битовую карту как и некоторые алгоримы сортировки можно применить не для всех данных, а автор имел ввиду непосредственно алгоритм. Я понимаю, что числа легче сравнивать, чем, например, строки. softwarerиз-за чего его используют только очень ленивые и глупые студенты (глупые - потому что не способны списать откуда-нибудь более удачную реализацию). А я наивно считал, что ленивые и глупые списывают... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.09.2006, 00:18 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=33987459&tid=1346581]: |
0ms |
get settings: |
10ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
46ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
37ms |
get tp. blocked users: |
1ms |
| others: | 271ms |
| total: | 396ms |
| 0 / 0 |
