Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 66
Разве учащиеся лицея не знают что такое предел?
В 10-х классах — нет. В 11 пока нет.
тогда ладно. сам пытался рассказывать интуитивную оценку сложности алгоритмов — без пределов это очень поверхностно осознается; казалось бы в простейших случаях ребята все понимают, но в более сложных рассуждая «по аналогии» совершают ошибки. у классов с базовым представлением о мат. анализе проблем не возникало.
Если уж товарищи заинтересовались алгоритмами, то можно было бы вкратце и объяснить, что такое предел. Благо, это несложно, но сугубо необходимо для дальнейшего роста.
тогда уж может вы расскажите? :)
Успеют они это выучить, моё дело дать самые основы.
Не надо основы подменять словоблудием.
> Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N).
А вас на этом месте никто не прервал вопросом «как определить формально скорость роста функции»?
> Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N).
А вас на этом месте никто не прервал вопросом «как определить формально скорость роста функции»?
Кстати, конкретно для обозначения O(f(n)) никакие пределы не нужны. Достаточно ограниченности сверху. Это уж точно можно объяснить.
учился в физ-мат школе, но в 10 классе предел понимается на отличненько. а как проходят производные без предела?
Почитал ради интереса «А как сейчас преподают сложность алгоритма?».
Лицей, Паскаль — в принципе для школьников самое то.
А вот насколько это «самое то» для крупнейшего IT-ресурса рунета?
Лицей, Паскаль — в принципе для школьников самое то.
А вот насколько это «самое то» для крупнейшего IT-ресурса рунета?
Я же говорю, может кому и будет интересно…
Вы, похоже, один из тех людей, которые готовы работать на голом энтузиазме.
Может Вам основать википедию для школьников?
Можно выбирать «класс» вместо языка и читать статьи доступным языком.
Кроме фактов, которые можно просто запомнить (например, даты из «истории»), если еще вещи, которые нужно понимать.
И без указания текущей базы в этом вопросе — никуда.
Может Вам основать википедию для школьников?
Можно выбирать «класс» вместо языка и читать статьи доступным языком.
Кроме фактов, которые можно просто запомнить (например, даты из «истории»), если еще вещи, которые нужно понимать.
И без указания текущей базы в этом вопросе — никуда.
А что, вы, простите, имеете против паскаля?
Вам сложность алгоритмов объяснять или в синтаксическом сахаре капаться?
Вам сложность алгоритмов объяснять или в синтаксическом сахаре капаться?
«Паскаль — в принципе для школьников самое то»
Где вы тут нашли нападки на паскаль?
Где вы тут нашли нападки на паскаль?
А вот насколько это «самое то» для крупнейшего IT-ресурса рунета?
Вот тут нашел, Вирт это не самое то для крупнейшего ИТ-ресурса?
Может все алгоритмы на MIXе стоит приводить? :)
Какая разница на каком языке написано, если вам не качество кода и не крутость алгоритма надо рассмотреть, а оценить его быстродействие?
Во первых: крутость алгоритма — это часто синоним эффективности и быстродействия.
Во вторых: с чего вы взяли, что я осуждаю паскаль? Он идеален для школьников. Для профессионалов я бы приводил описание алгоритма на псевдоязыке.
В третьих: в начале статьи рассматривается эффективность использования памяти, и по этому показателю паскаль отстает от других языков. Вспомните ступенчатые массивы например.
Во вторых: с чего вы взяли, что я осуждаю паскаль? Он идеален для школьников. Для профессионалов я бы приводил описание алгоритма на псевдоязыке.
В третьих: в начале статьи рассматривается эффективность использования памяти, и по этому показателю паскаль отстает от других языков. Вспомните ступенчатые массивы например.
Вы вообще понимаете о чём говорите, статью читали? У вас есть уже готовый алгоритм и вам надо оценить его сложность чтобы дальше уже принимать решения о его оптимизации.
С памятью то же самое. Вы оцениваете сколько этот алгоритм будет занимать, относительно более эффективных алгоритмов на этом же языке.
А псевдокод всегда менее понятен, чем старый-добрый, хорошо знакомый язык.
С памятью то же самое. Вы оцениваете сколько этот алгоритм будет занимать, относительно более эффективных алгоритмов на этом же языке.
А псевдокод всегда менее понятен, чем старый-добрый, хорошо знакомый язык.
Не в обиду будет сказано, но не все начинали с Паскаля. Я вот например совсем его не знаю. Но интуитивно догадался, что есть что =)
Отлично понимаю статью. И ни сколько ее не критикую.
Зачем эти нападки.
Вы можете реализовать алгоритм на любом языке.
Но по сути сам алгоритм — это последовательность действий и он независим от языка.
Паскаль не идеален. Кто-то начинал программировать на плюсах. Если тут начать приводить примеры на c++, школьники изучающие паскаль вряд ли поймут.
Зачем эти нападки.
Вы можете реализовать алгоритм на любом языке.
Но по сути сам алгоритм — это последовательность действий и он независим от языка.
Паскаль не идеален. Кто-то начинал программировать на плюсах. Если тут начать приводить примеры на c++, школьники изучающие паскаль вряд ли поймут.
А какоого рода, собственно, «псевдоязык» вы имеете в виду? Большая часть псевдоязыков, которые я видел напоминали сильно упрощённый… паскаль(!). Иногда что-то среднее между упрощённым паскалем и сями (без адресной арифметики, упаси господи). Так какая разница — упрощённый паскаль или просто паскаль? :)
А уж пассаж про эффективность использования памяти… Во-первых, при чём здесь язык, речь ведь об алгоритмах, а во-вторых, если говорить о «псевдоязыке», то о какой эффективности использования памяти языком(!) вообще может идти речь в этом случае???
А уж пассаж про эффективность использования памяти… Во-первых, при чём здесь язык, речь ведь об алгоритмах, а во-вторых, если говорить о «псевдоязыке», то о какой эффективности использования памяти языком(!) вообще может идти речь в этом случае???
Так здесь же школьников полно. Пусть учатся.
В чем проблема? Про новые свистелки и перделки в новом iPride 4GS можно написать на «крупнейшем IT ресурсе», а про основы теории сложности вычислений нет?
Вы бы код оформили нормально.
Мне кажется нехорошо константу отбрасывать… надо не по порядку оценивать сложность, а асимптотически…
(по-крайней мере меня так учили на теории алгоритмов=))
(по-крайней мере меня так учили на теории алгоритмов=))
А что считать одной операцией? Инструкцию процессора? Строчку кода? Важное свойство O()-нотации: она нечувствительна к (разумной) интерпретации одного языка программирования другим.
Не туда ответил=(, вот ответ: habrahabr.ru/blogs/algorithm/104219/#comment_3249247
А вам не кажется, что это слегка произвольный выбор? Почему выбор именно такой, а не какой-то иначе? Если уж решили заботиться о константе до конца, то нужно учитывать cache-эффекты, branch predictors и т. д. Да и, к примеру, сложения и умножения работают разное время.
Но в целом я согласен, бывает, что асимптотика лучше, но на практике алгоритм хуже (яркий примеры — перемножение матриц методом Штрассена, выбор медианы за детерминированное линейное время, Fibonacci heaps).
Но в целом я согласен, бывает, что асимптотика лучше, но на практике алгоритм хуже (яркий примеры — перемножение матриц методом Штрассена, выбор медианы за детерминированное линейное время, Fibonacci heaps).
Ну… в реальности работа того или иного алгоритма будет зависеть не только от языка, но и от процессора и его архитектуры, поэтому точно оценить совсем сложно становиться… Нам-то давали теорию алгоритмов с математическим уклоном, а не программистским. Но если приводить все алгоритмы к одной линейке (т.е. одному языку программирования), то константы оставлять стоит.
В зависимости от алгоритма: в алгоритмах умножения, мы одной операцией считали сложение, в сложение — логическую операцию и т.д. В более сложных алгоритмах типа возведения в степень и перемножения полиномов — уже операция умножения была базовой… Просто в некоторых случая константы такие, что при любых разумных n выгоднее использовать О(n^2), где константа 1, чем О(log(n)), где константа 9999999…
код нечитабелен, таблица в конце абсолютно неиформативна (что я должен узнать из неё?).
для школы может быть полезно, но я бы вообще построил рассказ чисто на примерах: вот есть такой алгоритм, а есть такой. какой лучше? как определить насколько один лучше другого? и + какие-нибудь известные алгоритмы и их сложности. имхо для школы будет достаточно.
ps. 1502 привет!
для школы может быть полезно, но я бы вообще построил рассказ чисто на примерах: вот есть такой алгоритм, а есть такой. какой лучше? как определить насколько один лучше другого? и + какие-нибудь известные алгоритмы и их сложности. имхо для школы будет достаточно.
ps. 1502 привет!
> Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.
Если мы храним запись для каждой пары точек, то даже при грязной реализации, когда для каждой пары точек две ячейки, общее число ячеек не превышает (10^4)^2 = 10^8 = 100 млн ячеек = (по вашему) = 100 Мб памяти. И не стоит городить огород =)
Ну это так, мелочи. Конечно, есть сложные задачи, и именно они интересны и стоят кучу денег, и именно ради них стоит дерзать.
Если мы храним запись для каждой пары точек, то даже при грязной реализации, когда для каждой пары точек две ячейки, общее число ячеек не превышает (10^4)^2 = 10^8 = 100 млн ячеек = (по вашему) = 100 Мб памяти. И не стоит городить огород =)
Ну это так, мелочи. Конечно, есть сложные задачи, и именно они интересны и стоят кучу денег, и именно ради них стоит дерзать.
Таблица времени выполнения алгоритма на основе оценки сложности алгоритма — Does not compute!
1) оформите код нормально — он нечитабелен
2) расскажите про гармоническое использование памяти + времени (чаще всего используется в задачах с использованием динамического программирования)
О да, я вот уже два года не могу решить придуманную мной задачу: нужно придумать задачу, которая будет иметь очевидное решение сложностью O(N^N).
2) расскажите про гармоническое использование памяти + времени (чаще всего используется в задачах с использованием динамического программирования)
О да, я вот уже два года не могу решить придуманную мной задачу: нужно придумать задачу, которая будет иметь очевидное решение сложностью O(N^N).
спасибо
Главное, чтобы ваше определение сложности, опирающееся на интуитивное понимание что такое программа, не противоречило общепринятому в терминах машины Тьюринга.
Запишите скринкаст :) За материал спасибо
я бы к топику добавил еще заметку про NP
расскажите, какими книжками пользовались при подготовке? Или что посоветуете посмотреть на эту тему еще?
у меня в институте был предмет в котором надо было оценивать сложность алгоритмов, но преподаватель сам плохо в этом разбирался, поэтому и нам ничего толком объяснить не сумел. А вам удалось :-) Спасибо. К слову, предмет я сдал «автоматов», т.к. с алгоритмами у меня все было в порядке :-)
А есть ли для matlab какой-то инструментарий для оценки сложности написанных в нем алгоритмов? возможность измерить время работы программы то есть, а вот выразить численно сложность… может кто в курсе?
Вы вот написали уже кучу довольно неплохих статей, ну разве нельзя постараться прилично их оформлять??? Вырви глаз же!
Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N).
Это определение неверно. О-большое — это верхняя оценка на время работы программы. А именно, говорят, что для функций f и g f=O(g) если существует такая константа c и число n0, что для любого n >= n0 верно 0 <= f(n) <= cg(n).
Гм, по Вашей системе получается, что, например, префикс-функция считается за кварат. Так что Вы пропустили достаточно большую часть теории оценки — амортизационный анализ.
Смысла нет уходить в О нотацию — без нешкольной математики слишком много голых фактов на веру. У того же Саттера есть объяснения сложности и времени выполнения где-то в начальных главах на вполне интуитивном уровне.
Смысл этой статьи? Если это обычная лекция ВУЗА. У нас в ВУЗЕ эта была 3 лекцией по предмету Алгоритмы и структуры данных.
Погодите, я не понял почему O(N^2 )*O(N^3 )=O(N^5) и O(N^2 )+O(N^3 )=O(N^3)?
Вы знаете, отучился в школе с углубленным изучением информатики, потом на инженера программиста в ВУЗе. В итоге только в ВУЗ дали какие то крупицы (как я после института понял на работе) сложности алгоритмов, вот такой бы материальчик в школе, просто и доступно, но уже много чего дает… В общем успехов с этим курсом, полезное дело, не то что для школы, для многих вузов.
Ооо, что то мне кажется… а это случайно не лицей 1502?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Оценка сложности алгоритмов