Здравствуйте, MTD, Вы писали:
BFE>>Обычно, всё-ж оценивают размеры обрабатываемых данных и временные рамки для их обработки, а не алгоритмическую сложность. MTD>Это оно и есть.
Нет. Время и количество шагов могут быть не связаны.
BFE>>Вот, например, кто-нибудь рассуждает так: "Окно в первом прототипе будет обрабатывать 5 сообщений. Количество сообщений по мере развития приложения может увеличится до сотни. Если мы напишем switch(номер сообщения), то алгоритмическая сложность составит O(n). MTD>Нет, оно составит О(1) и это очень круто, если так можно сделать, O(n) будет если будешь "форичить".
оно — это сложность?
поиск
switch(x)
{
case 1:
break;
case 2:
break;
case 3:
break;
...
case n:
break;
}
"равносилен", так как количество операций сравнений не меняется:
for(i = 0; i < n; i++)
if ( x == a[i] )
break;
Разве нет?
О(1) получится если считать данными количество сообщений. Если данными считать номер сообщения, то-нет.
BFE>>Но ведь есть алгоритм бинарного поиска! Его алгоритмическая сложность меньше. MTD>O(log n) — существенно больше O(1), но меньше O(n).
При n равным 100 ?
MTD>Это при условии, что добавление/удаление сообщений будет редко.
BFE>>Что-ж, заведём массив хранящий пару (номер сообщения, обработчик), отсортируем его по номеру сообщения и будем применять бинарный поиск! Тааак... теперь надо выбрать правильный алгоритм сортировки..." MTD>И на ровном месте превратим наш алгоритм в O(n * log n), что существенно больше O(log n).Обычно, всё-ж оценивают размеры обрабатываемых данных и временные рамки для их обработки, а не алгоритмическую сложность.
Похоже я вас "запутал". Я не предлагал сортировать очередь входящих сообщений. Пример неудачный. Извините.
Здравствуйте, B0FEE664, Вы писали:
BFE>>>Обычно, всё-ж оценивают размеры обрабатываемых данных и временные рамки для их обработки, а не алгоритмическую сложность. MTD>>Это оно и есть.
BFE>Нет. Время и количество шагов могут быть не связаны.
Еще как связаны.
BFE>"равносилен", так как количество операций сравнений не меняется:
BFE>
BFE>for(i = 0; i < n; i++)
BFE> if ( x == a[i] )
BFE> break;
BFE>
BFE>Разве нет?
Нет. Компилятор для свича построит таблицу переходов и вуаля — О(1)
BFE>>>Но ведь есть алгоритм бинарного поиска! Его алгоритмическая сложность меньше. MTD>>O(log n) — существенно больше O(1), но меньше O(n).
BFE>При n равным 100 ?
П.с. сам ни когда не знал как оно реализовано. Но если бы сам реализовывал, что-то вроде таблицы обязательно бы сделал — ибо сам по себе свич в коде — это некая форма таблицы.
Как один из критериев поиска кандидата — это наличие хоть какой-то фантазии.
Здравствуйте, _DAle_, Вы писали:
BFE>>Для известных алгоритмов оценка уже сделана. Осталось только выбрать. Вопрос же стоит о том, чтобы самому подсчитать сложность. На мой взгляд на практике это не делается практически никогда. _DA>Можно взять любой алгоритм, составленный из "известных". На практике — некий алгоритм с использованием стандартных контейнеров и библиотечных функций, там ведь уже надо как-то понять, какая сложность будет в результате. Или мы это не рассматриваем как "подсчет сложности"?
В моём понимании это не подсчет сложности. Вот пример: отсюда
Сама задача в данном случае не важна, но, на всякий случай: A>>Задача с собеседования: Есть два отсортированных массива, которые идут в памяти один за другим. Надо их слить inplace в один отсортированный массив за время O(n) и заведя O(1) дополнительной памяти.
Некий Аноним пишет: А>Затрудняюсь точно оценить время.. здесь сильно лучше O(n^2), вопрос насколько хуже O(n)?
Видите, Аноним не может вычислить алгоритмическая сложность этого своего творения (а только даёт оценку):
А>
А>public static void Sort(int[] source, int firstArrayIndex, int secondArrayIndex)
А>{
А> int i = firstArrayIndex, j = secondArrayIndex, k = -1;
А> while (true)
А> {
А> if (source[i] > source[j])
А> {
А> if (k == -1) k = i;
А> int temp = source[i];
А> source[i++] = source[j];
А> source[j++] = temp;
А> }
А> else
А> if (++i == j)
А> return;
А> if (j == source.Length || i == secondArrayIndex)
А> {
А> if (i == secondArrayIndex)
А> Sort(source, secondArrayIndex, j);
А> if (k + 1 < secondArrayIndex)
А> Sort(source, k + 1, secondArrayIndex);
А> return;
А> }
А> }
А>}
А>
а вы можете ? И часто занимаетесь этим на практике? Сомневаюсь.
ЕМНИП, у Кнута есть строчки, что для некоторых алгоритмов вычисление алгоритмической сложности — сама по себе задача не простая.
Здравствуйте, mefrill, Вы писали:
ПМ>>Ну я могу спросить, какая, например, сложность добавления элемента в конец ArrayList-а и в начало, и почему так получается.
M>Хороший вопрос, так видно собеседования и заваливают. Все же Array или List?
Здравствуйте, MTD, Вы писали:
BFE>>>>Обычно, всё-ж оценивают размеры обрабатываемых данных и временные рамки для их обработки, а не алгоритмическую сложность. MTD>>>Это оно и есть. BFE>>Нет. Время и количество шагов могут быть не связаны. MTD>Еще как связаны.
Количество шагов может быть огромным, а время выполнения ничтожным по сравнению с поставленными временными рамками. Так что это не важно.
BFE>>"равносилен", так как количество операций сравнений не меняется: BFE>>
BFE>>for(i = 0; i < n; i++)
BFE>> if ( x == a[i] )
BFE>> break;
BFE>>
BFE>>Разве нет? MTD>Нет. Компилятор для свича построит таблицу переходов и вуаля — О(1)
Интересно. Во всех случаях? Даже если константы идут не по возрастанию?:
switch(x)
{
case 1000:
break;
case -69876:
break;
case 834950:
break;
}
MTD>>>O(log n) — существенно больше O(1), но меньше O(n). BFE>>При n равным 100 ? MTD>Да.
Т.е. экономия сотни наносекунд в цикле обработки оконного сообщения — это нормально?
Здравствуйте, Злобастик, Вы писали:
З>Я вообще никогда в жизни не слышал о таком понятии, как "алгоритмическая сложность". Нигде — ни в институте, ни на работе, ни в книжках, ни в интернетах, ни от коллег.
Еще скажите, что на матане вы O-нотацию не проходили.
Здравствуйте, Паблик Морозов, Вы писали:
S>>Ну ежели вы спрашиваете просто на понимание о чём вообще речь, то ладно.
ПМ>Ну я могу спросить, какая, например, сложность добавления элемента в конец ArrayList-а и в начало, и почему так получается.
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, minorlogic, Вы писали:
M>>>>для "бугалтерий@документоообротом" Это все ен надо , да и ппрограмированием это с натяжкой нызывается. M>>>>Но с чего вы взяли что тут все документооборот клепают ? BFE>>>А в какой практической области это надо? M>>Начиная от оптимизации работы с большим к-вом данных, заканчивая 3д графикой. Или это ирония ?
BFE>Нет, не ирония. Я просто никогда не встречал программистов рассуждающих в терминах алгоритмической сложности для практических задач.
Это очень странно, может разные задачи у нас с вами. Я почти все время с такими общаюсь . Например на недавней пьянке спросил коллег оценить скорость выполнения двух вариантов инвертирования списков http://rsdn.ru/forum/job/4653211.1.aspx
Почти все предположили очевидные реализации и дали правильную оценку, с описанием когда лучше использовать тот или иной метод.
BFE> Например, при большом количестве данных обычно рассуждают не в терминах количества операций, а во временных затратах.
Которые могут быть оценены испольуя и алгоритмическую сложность. Вполне реально дать оценку , на каких типах данных и объемах какую лучше использовать сортировку radix sort или intro sort и т.п.
BFE>Сортировка данных лежащих на диске и сортировка данных находящихся в оперативной памяти — это два разных алгоритма. Рассуждения об о-большом тут мало чем помогут.
Еще как помогают, и оценка может быть сделанна достаточно строго. Примеры строгих оценок можно найти в соотв. литературе.
BFE> И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?
Здравствуйте, B0FEE664, Вы писали:
BFE>Вот не надо лукавить. Операции с листбоксом, скорее всего, не линейны — это раз. А решение о кастомизации принято не на основании алгоритмической сложности, а на основании размера данных, так как сама оценка сложности не изменилась.
Размер данных это тоже входит в оценку производительности. Но мульен операций O(N) и O(N*N) это небо и земля по быстродействию. И хоть издалека програмист видит эту разницу ибо азбука.
Здравствуйте, B0FEE664, Вы писали:
BFE>Но это не важно. Важно, что решение принятое вами о кастомизации основано не на оценке алгоритмической сложности, а потому, что "у него с ростом количества контента все тормозить начинает".
А решение о замене шин на автомобиле принимается после того как шина лопнет простите ?
Здравствуйте, B0FEE664, Вы писали:
BFE>Количество шагов может быть огромным, а время выполнения ничтожным по сравнению с поставленными временными рамками. Так что это не важно.
Количество шагов может быть небольшим, а время выполнения огромным по сравнению с поставленными временными рамками. Так что это важно.
BFE>Интересно. Во всех случаях? Даже если константы идут не по возрастанию?:
А какие проблемы?
BFE>Т.е. экономия сотни наносекунд в цикле обработки оконного сообщения — это нормально?
Экономия сотни наносекунд в цикле обработки 100 гигабитного потока — это очень хорошо! Смотри сам (я упрощенно): при 100 гигабитах, длительность 1 бита составит 0.01 наносекунды, а ты говоришь о сотнях наносекунд!
Здравствуйте, B0FEE664, Вы писали:
BFE>И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?
Ну вот как, как, такое может придти в голову? Я даже не об алгоритмах говорю, а о несчастных юзерах. Однозначно теперь первый вопрос про О-большое, ну после виртуального деструктора
Здравствуйте, MescalitoPeyot, Вы писали:
MP>Здравствуйте, Злобастик, Вы писали:
З>>Я вообще никогда в жизни не слышал о таком понятии, как "алгоритмическая сложность". Нигде — ни в институте, ни на работе, ни в книжках, ни в интернетах, ни от коллег.
MP>Еще скажите, что на матане вы O-нотацию не проходили.
Могу ошибаться, но в заборостроительных вузах вроде матана нет
Здравствуйте, B0FEE664, Вы писали:
BFE>Видите, Аноним не может вычислить алгоритмическая сложность этого своего творения (а только даёт оценку):
BFE>а вы можете ? И часто занимаетесь этим на практике? Сомневаюсь.
Есть такой метод — маляру дают задание покрасить 10 метров забора, он красит за 10 минут. Потом ему говорят покрасить 50 метров, он красит за 2500 минут, потом 100 метров, он красит за 10000 минут. Ага! По О(n^2) работает!
....
Продолжение. А почему? Выполняют анализ алгоритма — замечают, что он постоянно бегает к бочке с краской. Ок, ставят бочку на тележку, тележка едет рядом. Новые замеры: 10 метров — 10 минут, 50 метров — 50 минут, 100 метров — 100 минут. Вот другое дело — O(n)
Здравствуйте, B0FEE664, Вы писали:
BFE>Видите, Аноним не может вычислить алгоритмическая сложность этого своего творения (а только даёт оценку):
А>>
А>>public static void Sort(int[] source, int firstArrayIndex, int secondArrayIndex)
А>>{
А>> int i = firstArrayIndex, j = secondArrayIndex, k = -1;
А>> while (true)
А>> {
А>> if (source[i] > source[j])
А>> {
А>> if (k == -1) k = i;
А>> int temp = source[i];
А>> source[i++] = source[j];
А>> source[j++] = temp;
А>> }
А>> else
А>> if (++i == j)
А>> return;
А>> if (j == source.Length || i == secondArrayIndex)
А>> {
А>> if (i == secondArrayIndex)
А>> Sort(source, secondArrayIndex, j);
А>> if (k + 1 < secondArrayIndex)
А>> Sort(source, k + 1, secondArrayIndex);
А>> return;
А>> }
А>> }
А>>}
А>>
BFE>а вы можете ?
Этот код, во-первых, содержит ошибки типа выхода за пределы массива, а, во-вторых, вообще не делает то, что должен был (сливать два отсортированных массива).
Тест вот такой: Sort([2,3,4,5,1,2,3,4], 0, 4).
Далее, он использует естественно не O(1) памяти, так как глубину рекурсии здесь можно сделать хоть O(n), а стек — это естественно та же память, тест для такого вырождения примерно такой:
Sort([1,2,3,4,5,0], 0, 5)
Считать здесь сложность при наличии вороха ошибок — это издевательство ) При одних изменениях в алгоритме здесь будет одна сложность, при других — другая.
BFE>И часто занимаетесь этим на практике? Сомневаюсь.
Занимаюсь этим на практике. Не часто, но бывает.
BFE>ЕМНИП, у Кнута есть строчки, что для некоторых алгоритмов вычисление алгоритмической сложности — сама по себе задача не простая.
Здравствуйте, Sorc17, Вы писали:
S>"Спасибо, мы вам перезвоним в ближайшее время?"
Я не устраиваю собеседований в онлайне на rsdn, но когда мне так отвечают, я интересуюсь, как именно устроен ArrayList. В 100% случаев не отвечают. Дальше, как правило, следует еще пяток неверных ответов по основам используемой платформы, пяток неверных ответов по поводу специфичных вещей, нужных для проекта и, как правило, "спасибо, мы вам перезвоним в ближайшее время". Поэтому я и говорю, что всякие вычислительные сложности — это индикаторы. Если по ним незачёт, то дальше можно не продолжать, с высокой вероятностью ничего не потеряете, но сэкономите время.
