Pull to refresh

Comments 66

Разве учащиеся лицея не знают что такое предел?
В 10-х классах — нет. В 11 пока нет.
тогда ладно. сам пытался рассказывать интуитивную оценку сложности алгоритмов — без пределов это очень поверхностно осознается; казалось бы в простейших случаях ребята все понимают, но в более сложных рассуждая «по аналогии» совершают ошибки. у классов с базовым представлением о мат. анализе проблем не возникало.
Если уж товарищи заинтересовались алгоритмами, то можно было бы вкратце и объяснить, что такое предел. Благо, это несложно, но сугубо необходимо для дальнейшего роста.
На этот счет есть полно хороших книжек (к примеру, Introduction to Algorithms Кормена и компании). Читайте, и да будет вам просветление.
очень просто отсылать к книге, не попробовав объяснить на пальцах самому
Я сам не пробовал школьникам объяснять, что такое предел, но мне в десятом классе это прекрасно объяснили абсолютно строго (нет, я не учился в мат. классе).
Назвался груздем — полезай в кузов.
Успеют они это выучить, моё дело дать самые основы.
Не надо основы подменять словоблудием.

> Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N).

А вас на этом месте никто не прервал вопросом «как определить формально скорость роста функции»?
Кстати, конкретно для обозначения O(f(n)) никакие пределы не нужны. Достаточно ограниченности сверху. Это уж точно можно объяснить.
учился в физ-мат школе, но в 10 классе предел понимается на отличненько. а как проходят производные без предела?
Почитал ради интереса «А как сейчас преподают сложность алгоритма?».
Лицей, Паскаль — в принципе для школьников самое то.

А вот насколько это «самое то» для крупнейшего IT-ресурса рунета?

Я же говорю, может кому и будет интересно…
Вы, похоже, один из тех людей, которые готовы работать на голом энтузиазме.
Может Вам основать википедию для школьников?
Можно выбирать «класс» вместо языка и читать статьи доступным языком.

Кроме фактов, которые можно просто запомнить (например, даты из «истории»), если еще вещи, которые нужно понимать.
И без указания текущей базы в этом вопросе — никуда.

Где вы тут ведите сарказм, господа?
Хотя если действительно не согласны с необходимостью доступных статей для школьников…
А что, вы, простите, имеете против паскаля?
Вам сложность алгоритмов объяснять или в синтаксическом сахаре капаться?
«Паскаль — в принципе для школьников самое то»
Где вы тут нашли нападки на паскаль?
А вот насколько это «самое то» для крупнейшего IT-ресурса рунета?

Вот тут нашел, Вирт это не самое то для крупнейшего ИТ-ресурса?
Может все алгоритмы на MIXе стоит приводить? :)
Хватит выискивать нападки там где их нет.

Статья рассчитана на школьников 9-10 классов.
ИМХО, все кто читает хабр отлично знают этот материал.
>Статья рассчитана на школьников 9-10 классов.
ИМХО, все кто читает хабр отлично знают этот материал.


На Хабре полно школьников 9-10 классов.
// К.О.
Мне вот как раз впервые хабр показали одиннадцатиклассники Fenniks и NotXakep, когда я учился в 10 классе физ-мат лицея.

PS: Хороший пост, внес свою долю в подготовке к завтрашней пересдачи Анализа и разработки алгоритмов :)
Какая разница на каком языке написано, если вам не качество кода и не крутость алгоритма надо рассмотреть, а оценить его быстродействие?
Во первых: крутость алгоритма — это часто синоним эффективности и быстродействия.
Во вторых: с чего вы взяли, что я осуждаю паскаль? Он идеален для школьников. Для профессионалов я бы приводил описание алгоритма на псевдоязыке.
В третьих: в начале статьи рассматривается эффективность использования памяти, и по этому показателю паскаль отстает от других языков. Вспомните ступенчатые массивы например.
Вы вообще понимаете о чём говорите, статью читали? У вас есть уже готовый алгоритм и вам надо оценить его сложность чтобы дальше уже принимать решения о его оптимизации.

С памятью то же самое. Вы оцениваете сколько этот алгоритм будет занимать, относительно более эффективных алгоритмов на этом же языке.

А псевдокод всегда менее понятен, чем старый-добрый, хорошо знакомый язык.
Не в обиду будет сказано, но не все начинали с Паскаля. Я вот например совсем его не знаю. Но интуитивно догадался, что есть что =)
Отлично понимаю статью. И ни сколько ее не критикую.
Зачем эти нападки.

Вы можете реализовать алгоритм на любом языке.
Но по сути сам алгоритм — это последовательность действий и он независим от языка.

Паскаль не идеален. Кто-то начинал программировать на плюсах. Если тут начать приводить примеры на c++, школьники изучающие паскаль вряд ли поймут.
А какоого рода, собственно, «псевдоязык» вы имеете в виду? Большая часть псевдоязыков, которые я видел напоминали сильно упрощённый… паскаль(!). Иногда что-то среднее между упрощённым паскалем и сями (без адресной арифметики, упаси господи). Так какая разница — упрощённый паскаль или просто паскаль? :)
А уж пассаж про эффективность использования памяти… Во-первых, при чём здесь язык, речь ведь об алгоритмах, а во-вторых, если говорить о «псевдоязыке», то о какой эффективности использования памяти языком(!) вообще может идти речь в этом случае???
В чем проблема? Про новые свистелки и перделки в новом iPride 4GS можно написать на «крупнейшем IT ресурсе», а про основы теории сложности вычислений нет?
Мне кажется нехорошо константу отбрасывать… надо не по порядку оценивать сложность, а асимптотически…
(по-крайней мере меня так учили на теории алгоритмов=))
А что считать одной операцией? Инструкцию процессора? Строчку кода? Важное свойство O()-нотации: она нечувствительна к (разумной) интерпретации одного языка программирования другим.
А вам не кажется, что это слегка произвольный выбор? Почему выбор именно такой, а не какой-то иначе? Если уж решили заботиться о константе до конца, то нужно учитывать cache-эффекты, branch predictors и т. д. Да и, к примеру, сложения и умножения работают разное время.

Но в целом я согласен, бывает, что асимптотика лучше, но на практике алгоритм хуже (яркий примеры — перемножение матриц методом Штрассена, выбор медианы за детерминированное линейное время, Fibonacci heaps).
Ну… в реальности работа того или иного алгоритма будет зависеть не только от языка, но и от процессора и его архитектуры, поэтому точно оценить совсем сложно становиться… Нам-то давали теорию алгоритмов с математическим уклоном, а не программистским. Но если приводить все алгоритмы к одной линейке (т.е. одному языку программирования), то константы оставлять стоит.
В зависимости от алгоритма: в алгоритмах умножения, мы одной операцией считали сложение, в сложение — логическую операцию и т.д. В более сложных алгоритмах типа возведения в степень и перемножения полиномов — уже операция умножения была базовой… Просто в некоторых случая константы такие, что при любых разумных n выгоднее использовать О(n^2), где константа 1, чем О(log(n)), где константа 9999999…
О показывает характер зависимости некоей условной «сложности» алгоритма в зависимости от «размера» задачи (входных данных). То есть, насколько вырастет потребность в ресурсах, если объем входных данных изменится.
код нечитабелен, таблица в конце абсолютно неиформативна (что я должен узнать из неё?).

для школы может быть полезно, но я бы вообще построил рассказ чисто на примерах: вот есть такой алгоритм, а есть такой. какой лучше? как определить насколько один лучше другого? и + какие-нибудь известные алгоритмы и их сложности. имхо для школы будет достаточно.

ps. 1502 привет!
> Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.

Если мы храним запись для каждой пары точек, то даже при грязной реализации, когда для каждой пары точек две ячейки, общее число ячеек не превышает (10^4)^2 = 10^8 = 100 млн ячеек = (по вашему) = 100 Мб памяти. И не стоит городить огород =)

Ну это так, мелочи. Конечно, есть сложные задачи, и именно они интересны и стоят кучу денег, и именно ради них стоит дерзать.
Таблица времени выполнения алгоритма на основе оценки сложности алгоритма — Does not compute!
1) оформите код нормально — он нечитабелен
2) расскажите про гармоническое использование памяти + времени (чаще всего используется в задачах с использованием динамического программирования)

О да, я вот уже два года не могу решить придуманную мной задачу: нужно придумать задачу, которая будет иметь очевидное решение сложностью O(N^N).
Дано N чисел. Задача выписать все последовательности длины N из этих чисел, повторения допускаются.
Видимо, хотелось, чтобы результат был полиномиален по длине входа.

Ну пусть будет такая задача: дана N-1 функция f_i: {1, ..., N}^2 -> R. Нужно найти последовательность a_1, a_2, ..., a_N такую, что f_1(a_1, a_2) + f_2(a_2, a_3) +… + f_{N-1}(a_{N-1}, a_N) -> max
Главное, чтобы ваше определение сложности, опирающееся на интуитивное понимание что такое программа, не противоречило общепринятому в терминах машины Тьюринга.
расскажите, какими книжками пользовались при подготовке? Или что посоветуете посмотреть на эту тему еще?
«Алгоритмы: построение и анализ», Кормен, Лейзерсон, Ривест, Штейн
у меня в институте был предмет в котором надо было оценивать сложность алгоритмов, но преподаватель сам плохо в этом разбирался, поэтому и нам ничего толком объяснить не сумел. А вам удалось :-) Спасибо. К слову, предмет я сдал «автоматов», т.к. с алгоритмами у меня все было в порядке :-)
А есть ли для 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?
Я там учился и посещал этот курс, кажется это был год, когда вы начинались читать этот курс. Хабр тесен.
Only those users with full accounts are able to leave comments. Log in, please.