ANTICHAT — форум по информационной безопасности, OSINT и технологиям
ANTICHAT — русскоязычное сообщество по безопасности, OSINT и программированию.
Форум ранее работал на доменах antichat.ru, antichat.com и antichat.club,
и теперь снова доступен на новом адресе —
forum.antichat.xyz.
Форум восстановлен и продолжает развитие: доступны архивные темы, добавляются новые обсуждения и материалы.
⚠️ Старые аккаунты восстановить невозможно — необходимо зарегистрироваться заново.
 |
|
18.10.2009, 21:40
|
|
Участник форума
Регистрация: 01.01.2009
Сообщений: 144
Провел на форуме:
89680
Репутация:
154
|
|
Сообщение от desTiny
>>книга насыщена математическими выкладками
А что же такое "анализ алгоритмов" без математики?
и не надо аппелировать к термину "класс задач" - у него немного другой смысл.
Согласен, выполнять анализ без математических методов трудно. Но здесь это не требуется - достаточно написать конечные результаты и сделать по ним выводы.
Прошу Вас дать свой вариант определения "класса задач", чтобы заполнить пробел.
Последний раз редактировалось c0n Difesa; 18.10.2009 в 22:42..
|
|
|
18.10.2009, 22:35
|
|
Постоянный
Регистрация: 09.06.2005
Сообщений: 531
Провел на форуме:
3516666
Репутация:
439
|
|
Сообщение от c0n Difesa
"Аппелировать" - всмысле использовать?
Аппелировать = обращаться))
|
|
|
|
18.10.2009, 23:07
|
|
Reservists Of Antichat - Level 6
Регистрация: 04.02.2007
Сообщений: 1,152
Провел на форуме:
3008839
Репутация:
1502
|
|
под классом задач обычно понимают http://ru.wikipedia.org/wiki/Класс_сложности
>>достаточно написать конечные результаты и сделать по ним выводы.
так напиши полезные результаты (а не пузырёк), и полные выводы. Например, сколько в среднем (по всем входным массивам) работает тот же пузырёк, и сколько обменов он совершает в среднем?
__________________
Bedankt euch dafür bei euch selbst.
H_2(S^3/((z1, z2)~(exp(2pi*i/p)z1, exp(2pi*q*i/p)z2)))=Z/pZ
|
|
|
|
18.10.2009, 23:19
|
|
Участник форума
Регистрация: 01.01.2009
Сообщений: 144
Провел на форуме:
89680
Репутация:
154
|
|
Сообщение от desTiny
под классом задач обычно понимают http://ru.wikipedia.org/wiki/Класс_сложности
>>достаточно написать конечные результаты и сделать по ним выводы.
так напиши полезные результаты (а не пузырёк), и полные выводы. Например, сколько в среднем (по всем входным массивам) работает тот же пузырёк, и сколько обменов он совершает в среднем?
Из Википедии:
В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления.
Чтобы не быть голословным, объясните, где в своих постах я использовал данный термин не "по назначению".
Я понимаю что метрика "среднего случая" для Вас крайне важна, но не настолько, чтобы она стояла по приоритетам выше "худший случай" и "лучший случай", которых вполне достаточно для сравнения алгоритмов по эффективности.
|
|
|
|
18.10.2009, 23:54
|
|
Reservists Of Antichat - Level 6
Регистрация: 04.02.2007
Сообщений: 1,152
Провел на форуме:
3008839
Репутация:
1502
|
|
>>где в своих постах я использовал данный термин не "по назначению".
Существует множество способов решения определенной задачи (класса задач). Это множество порождает обилие алгоритмов, которые ее решают. Однако из этого набора алгоритмов можно выбрать те, которые справляются с поставленной задачей (классом задач) быстрее остальных, используя меньше ресурсов процессора и /или оперативной памяти.
Цель данного топика: рассмотреть как можно больше алгоритмов, оценить их временную сложность и определить границы эффективного применения. Границы эффективного применения – класс задач, для которого рассматриваемый алгоритм будет наиболее быстродейственным.
Один алгоритм (или "способ решения") к классу задач нельзя применить. Класс задач лишь говорит, что например, заача решается за полиномиальное время. Но если за полиномиальное время можно и посадить картошку, и собрать яблоки - это не значит, что это делается одним и тем же способом.
тут под классом задач, как я понимаю, имеется в виду "похожие по смыслу задачи". А, например, для похожих по смыслу задач проверки числа на простоту (невероятностного) и разложения на множители, первая имеет быстрое решение (логарифм числа в какой-то степени), а про вторую существование быстрого решения неизвестно.
>>которых вполне достаточно для сравнения алгоритмов по эффективности.
недостаточно. Вот почему, по-вашему, так часто пишут qsort, хотя худший случай это N^2, а не merge - с N log N ? А потому что, очень часто (читай - на случайном входе) быстродействие первого оказывается не хуже второго, а часто - лучше.
__________________
Bedankt euch dafür bei euch selbst.
H_2(S^3/((z1, z2)~(exp(2pi*i/p)z1, exp(2pi*q*i/p)z2)))=Z/pZ
|
|
|
|
19.10.2009, 14:08
|
|
Новичок
Регистрация: 14.03.2009
Сообщений: 25
Провел на форуме:
72034
Репутация:
5
|
|
Сообщение от desTiny
недостаточно. Вот почему, по-вашему, так часто пишут qsort, хотя худший случай это N^2, а не merge - с N log N ? А потому что, очень часто (читай - на случайном входе) быстродействие первого оказывается не хуже второго, а часто - лучше.
Для алгоритмов, уже описанных в этом топике, оценка среднего случая не так важна, тк в каждом из них она ближе к худшему случаю.
А о сортировках из вашего примера (быстрой и слиянием) автор еще не упоминал, и я уверен, что когда он это сделает, то мы увидим оценку их временной сложности в среднем случае 
|
|
|
|
19.10.2009, 14:34
|
|
Moderator - Level 7
Регистрация: 02.05.2009
Сообщений: 894
Провел на форуме:
4297091
Репутация:
2261
|
|
Кнута не читал и пока не собираюсь.
Эта статья интерсна, и чем больше в ней ставрительных характеристик тем лучше.
Если будут выкладки из чего-либо кроме википедии - будет вообще perfect |
|
|
|
19.10.2009, 14:47
|
|
Участник форума
Регистрация: 01.01.2009
Сообщений: 144
Провел на форуме:
89680
Репутация:
154
|
|
Сообщение от desTiny
тут под классом задач, как я понимаю, имеется в виду "похожие по смыслу задачи"
Под классом задач тут понимается именно похожие по сложности задачи. Например схожие по размеру и степени упорядоченности массивы.
недостаточно. Вот почему, по-вашему, так часто пишут qsort, хотя худший случай это N^2, а не merge - с N log N ?
Приведенные Вами алгоритмы сортировок я еще не успел рассмотреть. Повторюсь еще раз (и как заметил, Nikituki): в уже рассмотренных алгоритмах средний случай эквивалентен худшему. Ваше замечание я учту в дальнейших обзорах и средний случай буду рассматривать отдельно.
Сообщение от ErrorNeo
Кнута не читал и пока не собираюсь.
Эта статья интерсна, и чем больше в ней ставрительных характеристик тем лучше.
Если будут выкладки из чего-либо кроме википедии - будет вообще perfect
Будет еще замечательней, если другие также будут выкладывать свои алгоритмы (не только базовые, коих хватает в Википедии) с их обзорами.
|
|
|
|
Циклический сдвиг элементов массива вправо на k позиций |
19.10.2009, 15:21
|
|
Новичок
Регистрация: 14.03.2009
Сообщений: 25
Провел на форуме:
72034
Репутация:
5
|
|
Циклический сдвиг элементов массива вправо на k позиций
Сообщение от c0n Difesa
Будет еще замечательней, если другие также будут выкладывать свои алгоритмы (не только базовые, коих хватает в Википедии) с их обзорами. Ну чтож, попробую, мб кому-нибудь пригодится=)
Циклический сдвиг элементов массива вправо на k позиций
1) Код:
Код:
template <typename MassiveType>
void Shift(MassiveType *Massive, int MassiveLen, int k)
{
Reverse(Massive,0,MassiveLen-1); //разворачиваем массив
Reverse(Massive,0,k-1); //разворачиваем первые к элементов
Reverse(Massive,k,MassiveLen-1); //разворачиваем последние n-k эллементов
}
template <typename MassiveType>
void Reverse(MassiveType *Massive, int StartElem, int FinishElem)
{
int i;
MassiveType tresh;
for (i=0;i<=(FinishElem-StartElem)/2;i++)
{
tresh=Massive[StartElem+i];
Massive[StartElem+i]=Massive[FinishElem-i];
Massive[FinishElem-i]=tresh;
}
}
2) Особенности:
Не используется выделение больших объемов дополнительной памяти.
3) Временная сложность:
Во всех случаях Т(n) = О(N)
Последний раз редактировалось Nikituki; 19.10.2009 в 15:33..
|
|
|
|
|
|
|
|
Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
|
|
|
|
Линейный вид
