Comments 87
Ваше предложение оценивать производительность алгоритмов постфактум, тестами — порочно. Откуда вы будете знать какие вообще алгоритмы реализовывать, чтобы потестить?
Ваше замечание ровно о том, что я написал в конце. Вы хотите иметь не математический инструмент, а дельфийского оракула: Вы к нему с задачей — он Вам алгоритм, ну или хотя бы «посмотри сюда, сравни это — и будет тебе счастье», как в справочнике слесаря-сантехника. Не бывает так, нет здесь серебряной пули и нормальный теоретический анализ алгоритма требует подходить к нему больше, чем с одного бока. Не можете провести такой анализ — используйте экспериментальные методы исследования. Не можете или не хотите делать ни того, ни другого — пользуйтесь эмпирическими рекомендациями в руководствах по языкам программирования. Можете выполнить и то, и другое — вообще золотой специалист.
> Для написания программ под x86 пользы от машины Тьюринга и впрямь никакой, она не для этого и делалась. А вот для доказательства алгоритмической неразрешимости некоторых задач она очень даже кстати,
А вы не задумывались, зачем появилась в информатике О-большая нотация, когда уже была абстракция машины Тьюринга? Ведь последнего достаточно для рассуждений о вычислимости? Как оказалось, абстракция машины Тьюринга совершенно не подходит для оценки производительности алгоритмов на актуальном железе. И вот ввели новый инструмент, чисто для того, чтобы найти адекватный способ измерения производительности, подходящий для реального железа того периода.
Время идёт, новое железо уже совсем не похоже на старое. Понемногу, в деталях, оно трансформировалось в нечто, нарушающее все принципы машины фон-Неймана. Пора, соответственно, и математический аппарат подтянуть. Добавить новую, актуальную абстракцию. А старую модель оставить истории и теории, там же, где сейчас находится машина Тьюринга. Кстати, последнее время тьюринг-полноту принято показывать не приведением к оригинальной машине, а вычислением rule 110.
И задача теоретиков от computer science предоставить для практиков новую абстракцию, удобную к современному применению. Вы ведь не называете жалкими недоучками тех программистов, которые опираются (опирались когда это было актуально) на классические алгоритмы и их оценки?
Так получилось, что я эти вопросы знаю. Машина Тьюринга в принципе не предназначена для ответа на вопросы о вычислительной сложности, она предназначалась для получения строгого ответа на вопросы «что есть алгоритм?» и какой «класс задач можно решить чисто механически?». О-нотация появилась совсем не в связи с алгоритмами, а с изучением введенных Пуанкаре асимптотических рядов. Просто так получилось, что при анализе вычислительной сложности эта нотация обычно оказывается достаточно удобной. Она позволяет упростить анализ, исключая по мере надобности лишние множители. Это вообще никак не связано с реальным железом, только лишь с удобством вычислений. Так что не надо валить все в кучу.
Машины Тьюринга и архитектура фон Неймана вещи мало связанные и нарушение принципов второй никак не сказывается на первой. Чем стара эта модель, тем что не удовлетворяет вашим потребностям как специалиста-практика? Еще раз повторюсь, ее не для того придумывали. И свою историческую задачу она, вообще говоря выполнила. Для ответа на другие вопросы придумывались другие модели и приемы.
Но вы пытаетесь перевернуть все с ног на голову, ставя вопрос так, что вам нужен новый метод оценки старых алгоритмов. В самом основании этих «старых» алгоритмов лежали базовые упрощения действительности типа линейной модели памяти, и анализ их асимптотического поведения шел рука об руку с процессом их формулировки. Этот процесс не работает так, что вот мы что-то придумали — и давай его анализировать методами асимптотического анализа. Вас не устраивает, как старые алгоритмы ложатся на новое железо? Так садитесь и придумывайте новые. Но зачем же ставить CS-никам не свойственные им задачи потому, что такая их формулировка кажется Вам правильной?
Именно. А для чего ещё математика нужна?
> О-нотация появилась совсем не в связи с алгоритмами
Ну да. А теория категорий появилась гораздо раньше хаскеля. Но притащили её в CS как раз любители функционального программирования, приспособив для своих нужд уже имеющуюся математическую абстракцию.
> Чем стара эта модель, тем что не удовлетворяет вашим потребностям как специалиста-практика?
Не учитывает локальность памяти.
> Так садитесь и придумывайте новые.
Там и без меня справляются. Уже лет десять как написали сортировку для видеокарт, например.
Проблема в том, что пора обновлять базовые абстракции и лексику. Язык ведь частично определяет мышление. Если нет термина, то соответствующее явление попадает в слепое пятно. Потому статьи, что вы цитировали, так полезны — заставляют обратить внимание на объективное явление. Дальше уже каждый по мере разумения корректирует свои представления. Говорит «а ведь и правда, есть такое дело», начинает по-новому смотреть на мир. Ну и предлагает остальным прозревшим разработать общую терминологию и общие решения для описанных проблем. Это как паттерны проектирования — полезны тем, что структурируют мысли и дают программистам общий язык.
Ну так и я об этом, О-нотация была привнесена как удобное средство описания и анализа. Реальное железо тут совсем не при чем, как и машины Тьюринга.
И не должна, потому что с точки зрения алгоритмической полноты это свойство не имеет значение.
А до прочтения этих статей факт того, что память разделена на несколько уровней, был от Вас сокрыт? Просто это не тот вопрос, который требует какого-то перелопачивания теории, поскольку те самые асимптотические оценки остаются, вообще говоря, справедливыми. Авторы процитированных мной статей банально не понимают, что такое асимптотические оценки, пытаются рассуждать о них в привычных для себя категориях и приходят к (первый) выводу, что, пардон, ну их нафиг, лучше доверять тестам, чутью и мануалам на библиотеки языка, и (второй) к какой-то нелепой, высосанной из пальца оценке с наукообразным ее обоснованием. И тут проблема в том, что никто никого не вводил в заблуждения — сами заблудились, воспринимая такие оценки не тем, чем они на самом деле являются, а как нечто монолитное.
Да, фактическое поведение временной сложности изменилось, стало более сложным — но учитывать такого рода нюансы в рамках общего подхода, пытаться на каждый случай делать модели и формулировать подходы — дело гиблое, тут больше на руку сыграет тот же статистический анализ. Такие проблемы не в ведении ученых — они для них пусты, а в зоне Вашей ответственности: оцените потребность программы в памяти, особенности естественной организации данных, характер ожидаемых обращений, а если в состоянии — особенности целевой архитектуры и алгоритмов управления памятью операционной системы. После этого можно прикинуть подходящую оценку сложности того или иного алгоритма, поднять имеющиеся рекомендации к применению функций выбранной библиотеки и принять конкретное инженерное решение. Если Вы хотите, чтобы эту работу сделали за Вас яйцеголовые, предоставив некоторую общую модель — слишком многого хотите.
А базовые абстракции и так обновляются, а точнее пополняются. Появляются модели вычислителей с распределенной памятью, grid-архитектурой и пр. В рамках этих моделей как раз и разрабатываются новые алгоритмы и методы анализа. Насчет языков соглашусь, такая проблема есть, хотя и не стоит пока очень уж остро.
Нет, конечно. Но я не задумывался во всей полноте о последствиях. Привык полагаться на асимптотические оценки.
> Да, фактическое поведение временной сложности изменилось, стало более сложным
Ага. Вместе с этим изменилась целевая функция оптимизации. Что предполагает необходимость замены некоторых классических алгоритмов на другие. И на стандартизацию работы с кешами. Необходимо уже как-то более осознанно подходить к кешированию памяти, доставать её из-под капота. Потому что, пока она пребывает исключительно под капотом компиляторов и шедулеров, её трудно учитывать.
> Тут больше на руку сыграет тот же статистический анализ.
Как вы будете статистически анализировать _алгоритмы_?
Вы, видимо, хотите поймать меня за руку на неточности определения. Уточнюсь. Можно использовать результаты статистического анализа программной реализации алгоритма. Или нескольких реализаций. Да хоть всех когда-либо написанных на всех известных человечеству архитектурах, если это позволит принять Вам обоснованное решение по выбору и алгоритма, и его конкретного программного воплощения.
Эта модель, придуманная ещё в середине девяностых, несколько более сложна, чем традиционная RAM, поэтому под неё разработано меньше алгоритмов. Так получается, я полагаю, потому что при решении ещё нерешённой задачи люди сначала предпочитают всесторонне рассмотреть её в близкой (и часто практической), но более простой обычной RAM, а уже потом смотрят на кэш/внешнюю память/параллелизм.
Асимптотические ряды известны со времён Ньютона и Бернулли. Пуанкаре лишь применил эту идею к конкретной задаче (как Фурье применил тригонометрические ряды, известные ещё Гиппарху, к задаче теплопроводности).
Тем не менее, метод известен именно как "метод Фурье", потому что ему принадлежит как системное изложение теории тригонометрических рядов, так и применение её к задачам математической физики. Чего не было сделано ни Эйлером, ни Бернулли, ни другими учёными, применявших разложение по тригонометрическому базису в своих работах. Аналогично, системное изложение теории асимптотических разложений начата в диссертации Стильтьеса (Stieltjes Th., Ann. de l'Ec, Norm. Sup. (3) 3, 201-258, 1886) и работе Пуанкаре (Poincare H., Acta Math, 8, 295-344, 1886). Хотя отдельные результаты по данному направлению были получены ранее Эйлером, Лапласом, Лежандром, - и их вклад ни в коей мере не предлагается умалить, - современную теорию асимптотических рядов отсчитывают именно от Пуанкаре. Также как дифференциальное исчисление мы отсчитываем от Ньютона и Лейбница, хотя отдельными его элементами пользовались задолго до этих прекрасных парней.
Здесь скорее более уместен вопрос о приписывании О-нотации именно Бахману и Ландау. В их упоминаемых как первоисточники трудах данная нотация используется как уже определённая. Но утверждать не стану, так как не владею немецким и не могу в необходимой степени воспринять материал. Пусть это останется на совести специалистов по асимптотическому анализу, которые дают соответствующие ссылки и используют именно такое наименование для данной нотации.
Принцип Стиглера/Арнольда/Фишера/Берри: ни одно научное открытие не было названо в честь его первооткрывателя, в том числе указанный принцип.
Не совсем понятен критерий современности. Если найдётся ещё более современное использование известного объекта, откроются новые факты, будут доказаны с его помощью новые теоремы, значит ли это, что этот старый известный объект следует переименовать? Или если при изложении этих объектов будет достигнут ещё более высокий уровень математической строгости? И где граница современности?
Мне кажется, эпопея с массовым переименованием давно известных объектов, происходившая в XIX - начале XX века, связана с массовым образованием и введением учебников, авторы которых особо не парились и часто стремились отразить патриотическую компоненту. Да, да: то самое системное изложение - то есть учебник.
Ни теория пределов Коши и критерий сходимости (создана Ньютоном и Николазом Оремом), ни соотношения Коши (Эйлер), ни задача Бертрана (решена Ньютоном, изложена в Началах), ни упомянутые ряды Фурье, известные от века, ни интеграл Римана (идея Архимеда, повторно изложена Ньютоном в Началах даже без претензии на первичность как нечто само по себе разумеющееся; этот пример вообще позорище: зачем Риману чужая слава?!), ни ряд Тейлора (создан Грегори/Ньютоном), ни формула Ньютона-Лейбница (придумана Барроу) не носят имена хотя бы документально подтверждённых первооткрывателей, опубликованные в научных журналах.
Не вижу большого смысла в излишне формальном подходе к термину "современный". Тут имеется ввиду только то, что в работе Пуанкаре впервые теория асимптотических рядов изложена последовательно и достаточно полно, чтобы её классифицировать как самостоятельную область математического знания. По этой причине в работах по данному направлению употребляется, например, термин "асимптотический в смысле Пуанкаре". И да, вполне возможно если будет достигнут более высокий уровень строгости или произойдёт нетривиальное обобщение, то будут говорить об теории асимптотических разложений кого-то другого. Не вижу в этом криминала. Также Колмогорова, совсем не безосновательно, часто упоминают как создателя современной теории вероятности - несмотря на то, что вероятность и статистика в целом сформировались как отдельная математическая дисциплина задолго до выхода в свет его работ.
Почему тогда Великая теорема Ферма не переименована в теорему Уайлса? Ведь Ферма даже не дал намёток доказательства, в отличие от других упомянутых случаев, когда первоавторы хотя бы намечали схему доказательства.
Конечно не безосновательно и на мой взгляд, так как Колмогорову принадлежит фундаментальная идея связи вероятности и интегрирования.
По тому же, почему проблемы Гильберта остаются проблемами Гильберта. Доказательство принадлежит Уайлсу. Формулировка теоремы - Ферма. Теорему обычно называют по имени того, кто сформулировал, а не доказал. Иначе на каждое оригинальное доказательство теорему заново именовать бы пришлось, что уже безумие.
Помилуйте, но только что вы утверждали, что достаточно известному объекту дать всего лишь новое определение или новое изложение, как это повод его переименовать. Согласитесь, новое изложение, новое определение даются, как правило, несколько легче, чем новое доказательство.
Более того, я впервые слышу, что доказательств теоремы Ферма существует столь много, что существует проблема с выбором наилучшего и наиболее оригинального автора.
Подведём итог.
Для того, чтобы дать новому или старому объекту имя исследователя достаточно, согласно предложенной вами концепции:
Решить принципиально новую задачу (математическую или естественно-научную) известным методом или дать полное изложение этого метода, или на тот момент, наиболее полное (Тейлор, Фурье, Пуанкаре).
Предложить формулировку теоремы или просто некоторой проблемы, даже сформулированной ещё не вполне точно, и не доказать её. Не нужно даже давать намёток доказательства: достаточно дать формулировку проблемы на полях салфетки (Ферма, Гильберт).
Быть достаточно известным, чтобы дали твоё имя.
В этих условиях нет ничего о "звенящей строгости" или "абсолютной корректности".
Все эти условия выполняются для Ньютона как для правил дифференцирования, так и в отношении определённого интеграла.
Не соглашусь, это зависит от ситуации. Введение подходящего понятийного аппарата бывает важнее, чем доказательство даже очень значимой теоремы в рамках уже разработанной теории. Хотя оценка «важности» всегда очень субъективна. Насколько могу судить, сам факт того, что Великая теорема Ферма получила наконец строгое доказательство, не послужил основой для значимого развития теории. Хотя принципиальную важность доказательства отрицать бессмысленно.
Про «множество доказательств» конкретной теоремы речи не было, в том числе Ферма. Я указываю только на то, что формулировка утверждения и его доказательство нередко могут выступать в качестве самостоятельных семантических единиц. Следовательно, именоваться они могут также раздельно. Могут, а не должны. Если доказательство достаточно оригинально или имеет самостоятельную, выходящую за рамки исходного утверждения ценность, то ему может быть дано самостоятельное название.
Я не выдвигал никаких концепций по именованию чего бы то ни было. Напротив, я утверждаю, что именование не следует и не может следовать какой-либо строгой концепции, в том числе основанной на некой абсолютной идеи авторства оригинальности. Не вижу никакого смысла в поиске чего-то похожего на «историческую справедливость» в этом вопросе, ровна как и в борьбе за оную. С позиции практического применения именование, например, определения мне видится вполне корректным, если именно оно сформулировано тем, чьё имя носит именно в той форме, которую применяющий данный термин автор использует в своей работе. Или формулировка автора не привносит ничего нового (ни концептуально, ни формально) в оригинальное определение. Использование термина «интеграл Римана» это не реверанс в сторону исторических заслуг Римана, это всего лишь неформальное соглашение, избавляющее от необходимости уточнять то определение интеграла, которое вы используете в своём изложении. А если вы напишите «интеграл Ньютона», то обязательно найдётся зануда типа меня, который попросит вас остановиться и уточнить, что конкретно вы имеете ввиду.
Короче, вещи называются так, как называются, и свои названия они получают в силу различных обстоятельств. Подводить под эти процессы искусственные концепции считаю нецелесообразным. Лично я не возражал бы против термина «интеграл Ньютона», поскольку и правда бывает затруднительно объяснить почему формула Ньютона-Лейбница, а сам интеграл Римана - логика подсказывает, что вроде как введение понятия должно хронологически предшествовать формулировке каких-либо утверждения относительно него. Однако история, в том числе науки, не так линейна.
Пассаж про патриотическую компоненту не понял. Копаться в исторической справедливости дело вообще малоперспективное. По моим ощущениям, вопрос названий связан не с тем, кому принадлежит право первооткрывателя, а с тем, благодаря чьим работам определенный результат стал известным. Или с тем, кого в качестве первооткрывателя назвал тот, кто сделал некий результат известным.
Возможно.
О, наука и научная приоритетность, - одна из главных проблем правительств. У одних интеграл Остроградского и какого-то-там Гаусса, у других в научном журнале публикуют анонимный клеветнический пасквиль в адрес Ньютона и вообще стараются избегать имён английских учёных, ну а третьи, они же первые, целые пласты объявляют "клеветнической лженаукой" и выдвигают своих шарлатанов, да и вообще любовь к тем или иным авторам определяется текущей конъюнктурой.
Если в 37 году Мордухай Болтовский комментировал математические работы Ньютона с плохо скрываемой стилистически выверенной злобой - не знаю, искренней, или официально индоктринированной, - ("Ньютон не понимал, да и не мог понять", "при таких обозначениях мысль о дробном дифференцировании, конечно, не могла появиться у Ньютона", "Ньютон, конечно, уравнение циклоиды не мог выразить в [в современных обозначениях] форме ...", "эти приёмы можно рассматривать как содержащие в самом неразвитом виде формулу Лагранжа", "Н. даже доходит до введения символа а, представляющего неопределённость первого члена [константы интегрирования ДУ], ... но это решение не выставляется как самое общее", "ясного представления об общем интеграле у Н. нет, и кроме примера 4, у Н. нигде не появляются произвольные постоянные", "как ни велики заслуги Н. в чистой математике, но они меньше, чем в прикладной", "техника дифференцирования и интегрирования представляется у Н. в сравнении с Эйлеровской очень примитивной", "конструктивная точка зрения вообще чужда Н., чего нельзя сказать о Лейбнице [к тому же это просто прямая ложь, см. теорему о квадрируемости гладких овалов]", "У Н. и его современников, для которых математика является орудием грубого примитивного вычисления ...", "Н. потенциально бесконечно малым ещё не овладел вполне [недоучился]" и т.п.), то в 1943 году тональность советских авторов при изложении трудов Ньютона или его биографии резко меняется на противоположную и становится экзальтрованно-превосходной.
Интересно, как будет в наши дни.
Если вы намекаете на лысенковщину, то это совсем не такой простой вопрос про то, как недалёкая советская власть в угоду политической конъюнктуре гнобила настоящую науку.
У нас теорема Котельникова, на западе Найквиста. Могу назвать кучу схожих или полностью эквивалентных результатов, полученных независимо в разных странах и, соответственно, маркированных разными именами. Это не политический вопрос. По крайней мере чаще всего.
Не замечал в советской литературе ни возвышенного, ни уничижительного тенденциозного отношения к Ньютону или какому-либо иному учёному. Да и в наши дни тоже. Вы точно не выдаёте частное за общее?
К философам - да, случается. К политическим деятелям тем паче. Но по отношению к учёным встречалась только критика, местами ожесточённая, но обусловленная исключительно отношением конкретного автора.
Что касается незаслуженной славы Римана, то в "Началах" Ньютона (удачно оказались на полке) понятие интеграла изложено неформально. Это не упрёк Ньютону. Но вы наверняка помните, что начиная со второй половины XIX века имела место существенная формализация математического знания. Имя в определении имеет целью не столько отдать дань уважения автору идеи, сколько указать откуда что-то излагающий гражданин взял определение, теорему или результат. Так что не вижу в этом ничего, что можно было бы вменить Риману в вину. Было бы странно действуя в рамках формальной теории ссылаться на неформальное определение - даже если все понимают их концептуальную тождественность.
Упаси боже: Римана никто не винит. Я критикую тех методистов, которые назвали это дело "ИР". Очень хорошо, что у вас Начала, и вы их читаете.
Но это не всё. Если бы Риман действительно занимался строгим (или более строгим) изложением теории определённого интеграла, я вряд ли бы написал эту критику. Более того, я абсолютно уверен, что именно в этом случае господин Риман в своём труде обязательно упомянул бы своих великих предшественников (трудно представить, чтобы такой учёный муж, как Риман, занялся бы таким делом, не ознакомившись с Началами и трудами Архимеда), причём упомянул исключительно в комплиментарном ключе. И тогда этот вид интеграла назвали бы "интегралом Римана-Ньютона" или "Римана-Архимеда".
Но Риман не занимался изложением теории определённого интеграла.
Риман занимался проблемами рядов Фурье, где применил этот интеграл.
Более того, я склонен согласиться с Арнольдом в том, что предпочтение как в авторстве, так и в изложении, следует отдавать не доказательствам, не формальным определениям, не борьбе за строгость, а идеям.
В рамках идей изложение Ньютона полно и полноценно. Можно указать лишь на неустоявшуюся терминологию, возможность более строгих доказательств, но рамочная схема определённого интеграла изложена полностью. Именно подобные результаты и сделали понятным то направление, куда следует двигаться на пути увеличения строгости.
Если же следовать максиме "было бы странно действуя в рамках формальной теории ссылаться на неформальное определение - даже если все понимают их концептуальную тождественность", то следует при наименовании математических теорем и проблем полностью отказаться от имён учёных, работавших до конца ХIХ века (даже Коши и Гаусса). Фактически, большинство названий будут отражать фамилии авторов текущих учебников, что не только странно, но даже и неприлично.
Я не в курсе того, был ли знаком Риман с трудами непосредственно Ньютона. У меня вовсе нет ничего похожего на абсолютную уверенность в этом вопросе - труды Ньютона и Архимеда имеют значение скорее историческое, нежели прикладное. Что-то полезное с точки зрения математического знания в них найти сложно. Лично у меня Ньютон и Евклид стоят на одной полке с Марксом и Витгенштейном.
Но это не имеет принципиального значения.
Мысль давать имена определениям, теоремам, законам и т.д. на основании первенства идеи привлекательна, но идеалистична. От какого момента мы будем отсчитывать идею? Можно авторство идеи отдавать хоть Ньютону, хоть Торричелли, хоть Архимеду, хоть Демокриту, хоть безымянным египтянам, пользовавшимся подобной техникой 4000 лет назад. Как справедливо отмечал В.И.Гливенко, интеграл является выражением различных способов измерения величин. То есть идея интегрирования и интеграла настолько естественна, что вообще представляется бессмысленным искать её первооткрывателя.
Нет, изложение Ньютона отнюдь не полно и не полноценно. На ограниченность подобного подхода указывали и Лагранж, и Лежандр, и Эйлер, и Гаусс, и многие-многие-многие. Им не казалось, что рамочная схема изложена полностью. Определение интеграла вводилось многократно, и все несколько отличались и друг от друга, и от "ньютоновского". Понятие интеграла имеет богатую историю развития, и с именем Римана его связывают только по той причине, что именно Риман дал то определение интеграла, которое используется в классическом анализе в его современном изложении. Оно формально не эквивалентно ни понятию, использованному Ньютоном, ни Эйлерову, ни определению Коши - который также разработал формальную теорию конкретно определённого интеграла, в явном виде определив множество интегрируемых функций.
В анализе вводится конкретное определение "интегрирование в смысле Римана". И в современной практике, если не сказано иное, видя знак интеграла с указанными пределами мы принимаем по-умолчанию, что это именно римановский интеграл, а не какой-то другой. Этим определением не исчерпывается понятие интеграла вообще. Ещё Колмогоров отмечал, что по-видемому нельзя создать сколь-нибудь общую теорию интегрирования Просто Риман дал такое определение, которое во многом оказалось удовлетворительным в практическом плане. Так что название оправдано.
Сложно, конечно, если не искать. Но можно. Навскидку:
Тихомиров. Аэродинамическая задача Ньютона.
Арнольд. Второй закон Кеплера и топология Абелевых интегралов.
Метод многоугольника Ньютона (обобщённый метод разложения в ряды с дробными степенями).
А в 19 веке великие французские учёные там могли найти россыпь замечательных и уже решённых к их счастью задач и назвать их своими именами. К слову, Эйнштейн читал не только Ньютона, но и Евклида ("Геометрия Евклида - это первая естественно-научная физическая теория пространства"). Не исключаю, что именно это глубокое знание предшественников сильно помогло Эйнштейну: в конце концов, именно Эйнштейн полностью завершил естественно-научную парадигму Ньютона, полностью ответив на заданные Ньютоном вопросы. Читать классиков иногда полезно для карьеры, а "снобизм современности" не всегда продуктивен.
Главная проблема таких названий методическая: название "интеграл Римана", "предел Коши" вводит людей, получающих образование, в глубокое заблуждение, создавая иллюзию, что до этих замечательных учёных мужей люди ничего толком не умели. Это всё равно, что назвать автомобиль не именем того, кто его сконструировал и собрал, кто на нём сделал первый шаг, а именем того, кто через сто лет доказал его "существование и единственность".
Все указанные различия малосущественны. Ньютон излагает интеграл так:
1. Лемма о трёх пределах ("о милиционерах", "Squeeze theorem").
2. Водит верхние и нижние суммы Дарбу (идея Архимеда) пока с равным разбиением и рассматривает предел этих сумм для ограниченной функции на отрезке.
3. Наконец, рассматривает случай, когда разбиение не однородно, но максимальный шаг разбиения стремится к нулю.
4. Указывает, что все эти пределы равны, в последнем случае - при любом разбиении, и в совокупности определяют площадь под кривой, то есть Ньютон определяет интеграл Римана по Дарбу.
Поясните, пожалуйста, чем эта теория определённого интеграла содержательно отличается от академической.
Конечно, некоторые, те или иные идеи и методы как чудесные разрозненные факты были известны и до Ньютона, а после было сделано много уточнений формулировок и строгость изложения повышена до звона в ушах. Однако именно у Ньютона изложение определённого интеграла приведено в точно существующем научном труде именно его авторства, а не в его лекциях, записанных учениками, систематически, объединив воедино всё то разрозненное, что было до него. В это изложение Ньютон привнёс новую до того незадокументированную идею предела, а сам интеграл использован Ньютоном для новых естественно-научных и метематических проблем.
Согласно вашим же определениям этого более чем достаточно для названия "определённый интеграл Ньютона". Все остальные уточняющие формулировки носят лишь методический характер из довольно скомпрометированной области "обоснование матанализа" и на фоне нововведений Ньютона откровенно мелки.
А вот в другом определении интеграла (Курцвейля-Хейнстока-Лузина-Данжуа-Перрона и т.п.) действительно упоминание Ньютона было бы неуместно, поскольку там содержится совершенно новая идея (определение вводится так, чтобы формула Ньютона-Лейбница выполнялась всегда), во всяком случае, до тех пор, пока эта идея не обнаружена в работах Ньютона (надо бы покопаться, сохранились и неопубликованные черновики). В классических же определениях интеграла новых идей по сравнению с изложением Ньютона нет.
Не особо понятно, в подкрепление какого тезиса приведены указанные работы. Что Ньютон молодец, рассмотревший некоторые задачи, которые в последствие всплыли в рамках достаточно современных научных теорий? Это вроде как и не оспаривалось. Более того, пример Ньютона в данном отношении далеко не уникален. История науки завалена результатами, которые предвосхищали будущее развитие научных представлений, причём получены эти результаты зачастую в совершенно ином контексте. Это происходило в XVIII в, происходит и в наше время. Совсем недавно знакомый рассказывал, что они буквально случайно обнаружили очень близкие к полученным ими результаты в работе середины прошлого века. По наноматериалам, хотя, казалось бы, какие в то время наноматериалы. Важным моментом в данном случае является не только сам результат, но и то, как он встроен в современную научную картину мира. Работы Ньютона в данном случае выделяет только то, что этот без сомнений выдающийся учёный одновременно имеет беспрецедентную степень известности, благодаря которой его работы изучаются с особым пристрастием.
Бывает. А ещё бывает полезным опыт игры в рулетку, водное поло, принятие стимулирующих веществ или баловство на музыкальном инструменте. На возникновение плодотворной идеи может оказать влияние хоть прочтение научной монографии, хоть исторического труда, хоть философского трактата, хоть сказа о Средиземье. А также вечерняя прогулка с милой дамой или созерцание отражения крыльев бабочки на поверхности озера. Я также не исключаю, что изучение трудов классиков может привести к более глубокому пониманию какой-то концепции и рождению нового научного знания. Но и оснований для подобных предположений о существовании хоть сколько-нибудь устойчивой зависимости между этими событиями не вижу - иначе наиболее выдающийся вклад в науку делали бы историки науки. В подобной форме снобизма меня обвинить сложно, поскольку как раз мне зачастую интересно проследить эволюцию представлений о том предмете, с которым приходится работать. Лично я считаю это чрезвычайно полезным. Но обобщать не рискну, поскольку в достаточном количестве знаком с весьма успешными исследователями, для которых подобное занятие никакого интереса не представляет.
Ввести таким образом в заблуждение можно только тех, кому в принципе история науки, да и сама наука, до лампочки. Уже поверхностно знакомые с темой граждане прекрасно понимают, что подобная обывательская логика тут не работает, а развитие науки не протекает линейно. С точкой зрения, что до XIX века ученые вообще и математики в частности ничего не знали и не умели не встречался ни разу. Скорее уж с такой, что до Ньютона никакой значимой науки вообще не было.
Поясняю.
Изложение интегрирования у Ньютона по-существу геометрическое, оно действительно обобщает идею Аристотеля, избавляя её от конкретного способа построения разбиения и оставляя только существенный момент о возможности устремления размера всех элементов разбиения к нулю. По факту Ньютон в своих рассуждениях не выходил за рамки гладких функций. Безусловным вкладом Ньютона также является то, что им в явном виде сформулирована связь между дифференциальным исчислением и интегрированием. Эта точка зрения - интегрирование через нахождение первообразной - была в известной степени доведена до завершения Эйлером и в течение долгого времени оставалась доминирующей.
Существенным же пробелом в подходе, указанном Ньютоном, является неявное требование непрерывности, ограниченности, а в некоторых случаях и гладкости интегрируемого выражения. То есть Ньютон рассматривая интегральные суммы каждый раз неявно предполагает, что в каждой конкретно рассматриваемой им задаче существует предел этих сумм и все проводимые им построения сохраняют смысл. Что, строго говоря, необходимо в таком случае каждый раз доказывать отдельно. А что предлагается делать, например, если интегрируемая кривая на заданном промежутке не является ограниченной или терпит разрыв? Это существенный момент, поскольку он нарушает представление об интеграле как о "сумме дифференциалов" и приводит к необходимости более скурпулезного использования термина "интегрирование" во избежание ошибок в построениях.
Идея построения предела интегральных сумм является общим местом для всех ранних теорий интегрирования - поскольку она естественна. Ньютон здесь разве что подвёл под неё достаточно прочный (по меркам своего времени) математический базис. В этом отношении его вклад в развитие данного понятия вряд ли можно считать выдающимся. Во всяком случае, на фоне выявления связи между интегрированием и дифференцированием. Пределы интегральных сумм выписывались в явном виде и Эйлером, и Пуассоном, и Бернулли, и очень многими другими, без ссылок на Ньютона. Не думаю, что из желания его принизить - в других вопросах его упоминанием не брезговали. Скорее как раз потому, что рассуждения аналогичные ньютоновским в данном вопросе представляются достаточно тривиальными и легко могли быть воспроизведены в том числе теми, кто с работами Ньютона знаком не был. Вопрос в конкретном указании условий существования предела интегральных сумм, без которого невозможно построение хоть сколь-нибудь общей теории. Это можно сделать, как в более ранних определениях - например, в определении интеграла Коши, - через явное указание класса функций, для которых вводится понятие интеграла. Отличие определения Римана в том, что не операция интегрирования вводится для определенного класса функций, а, напротив, определяется класс интегрируемых (в смысле Римана!) функций через явное указание условия: для каждого \epsilon > 0 найдётся такое число \delta > 0, что для любого разбиения P отрезка [a, b], такого, что \lambda(P) < \delta, выполняется
|I - \sum f(\xi_i) \Delta x_i| < \epsilon
где \lambda(P) -- максимальная из длин отрезков разбиения.
Этот класс функций включает в себя, в частности, класс непрерывных функций, для которых теорию интегрирования построил Коши. Но не ограничивается им.
Поскольку во многих практических случаях нам достаточно ограничиться именно классом интегрируемых в смысле Римана функций, то мы и используем именно римановское определение интеграла. Хотя могли бы и определением Коши во многих случаях ограничиться. Или вообще исходить из построения интегральной суммы и доказать существование предела конкретно в интересующем нас случае. Вопрос целесообразности, не более. Строгость, которая до звона в ушах, появилась не от того, что математикам было нечем себя занять, а из соображений практической целесообразности. Конкретное определение Римана более практично, чем основанное на геометрических соображениях определение Ньютона. И говорить, что в определении Римана не содержится ничего нового по сравнению с определением (которого, кстати, в явном виде дано и не было) Ньютона - это как говорить, что отснятый и смонтированный фильм ничем концептуально не отличается от своей раскадровки.
Ещё раз сформулирую свою мысль, чтобы не было разночтений. Интеграл носит имя Римана не потому, что Риман предложил какую-то чрезвычайно оригинальную формулировку или идею. Этого не было. Неформально все понимали понятие определенного интеграла более-менее одинаково ещё до того, как вообще были введены термины "определенный интеграл" и "пределы интегрирования". Необходимость же более формального подхода к определению вызвана строго практической необходимостью получения строго доказуемых результатов. Интеграл так назван потому, что при изложении анализа и в практических приложений используется именно то формальное! определение, которое было дано конкретно Риманом. И те результаты, которые следуют из этого формального определения. Лично мне кажется, что с практической точки зрения такой подход к выбору названий более оправдан. Когда я вижу в работе, например, упоминание какой-нибудь теоремы Васичкина, я обычно рассчитываю, что заглянув в соответствующую работу Васичкина я увижу именно ту формулировку, которую имел ввиду сославшийся на теорему автор. А не работу, где впроброс высказывалась идея, которая в последствие привело к использованной формулировке. Я конечно утрирую, но надеюсь, что посыл понятен.
Хотя, опять же, я не утверждаю, что во всех случаях можно и нужно придерживаться именно этого принципа.
И задача теоретиков от computer science предоставить для практиков новую абстракцию, удобную к современному применению
С чего вдруг теоретики должны под конкретную платформу предоставлять новые нотации? А универсальной нотации тут очевидно быть не может. Автор совершенно прав — мозгами думать просто надо а не на О-нотацию все валить.
В модели многоуровнего доступа к памяти используются те же самые O-оценки, просто с другим описанием того, что такое один шаг, лучше отражающим структуру кэшей. Почитайте, например про модель кэш-памяти, используемую при анализе таких алгоритмов. Она давным давно разработана теоретиками computer science, просто редко кому нужна и довольно непроста.
Пусть имеются конечный набор типов идеальных логических элементов («транзисторов» или схем, реализующих более сложные функции). Можно ли построить, пусть даже из бесконечного числа таких элементов, универсальную вычислительную машину с бесконечным адресным пространством и равномерно ограниченным временем доступа ко всем ячейкам памяти (конечного объема), если все логические элементы тратят ровно один ход на выполнения реализуемой ими функции, а сигнал между ними передается мгновенно?
Заметьте, что я снял все ограничения физического или экономического характера, тем не менее, бьюсь об заклад, что смогу перенумеровать ячейки памяти любой удовлетворяющей условиям машины так, что доступ к ним из начального состояния будет ограничен снизу по количеству шагов логарифмом их номера в моей нумерации.
Про необходимость ограниченности времени доступа к памяти некоторой константой нигде не говорилось, это бы противоречило допущению бесконечности памяти. Говорилось о том, что вводя такие понятия, как массив или линейный список обычно явно или неявно фиксируются базовые допущения, потом постулируются основные свойства и далее вводятся и параллельно оценивается сложность основных операций. Это значит, что говоря слово «массив» вы уже предполагаете одинаковое время доступа к произвольному элементу и только тогда имеете право опираться на полученные для массива оценки сложности. В случае иерархической организации памяти такие допущения приемлемы, если в среднем большая часть операций проводится на одном из уровней. Если же Вы понимаете, что у вас характер распределения данных и обращения к ним таков, что такие эффекты окажут существенное влияние на общий итог — ну так учтите это, рассмотрите такую организацию данных как другую структуру, свойства которой точнее отражают состояние дел. Так нет же, Вы хотите, чтобы кто-то за вас рассмотрел «массив» в устраивающем именно Вас смысле этого слова. Поймите, это вообще не задача тех, кто занимается исследованием алгоритмов и теорией вычислений, учет нюансов целевой архитектуры — это задача в первую очередь разработчиков операционных систем и компиляторов. Это они озадачены тем, как наиболее эффективно спроецировать алгоритмы, сформулированные в терминах удобной для использования и исследования модели, на реальное железо. Если Вам не нравятся их решения — берите в руки спецификацию на процессор и делайте всё сами. Вот если действующая модель принципиально не ложится на конкретный набор железа хоть сколь-нибудь эффективно как, например, в случае гетерогенных распределенных вычислительных систем — вот тут в игру вступают дядьки в очках на носу и с мелом в руках и вводят в рассмотрение новые модели и методы. А вопросы, на которых Вы пытаетесь заострить внимание, вполне в компетенции инженеров (должны быть, по крайней мере) и для теоретиков большого интереса не представляют.
Пусть имеется процессор и оперативная память размера N, соединенная с ним шиной. Невозможно обработать запрос на доступ к ячейке памяти в среднем быстрее чем за полином от логарифма N срабатываний элементарных логических элементов, из которых набрана шина. Если дела внутри процессора намного хуже, то эта оговорка не имеет значения, но в случае специализированных вычислений может иметь смысл так сегментировано организовать память, чтобы в каждом сегменте адресов было поменьше.
Ваш «логарифм», который «выстрелит» — это придумка, поправка, которой Вы надеетесь компенсировать разницу между своим собственным восприятием теории и наблюдаемой практикой. Вводя такие поправки Вы в первую голову себя вводите в заблуждения, думая, что раз Вы все еще пользуетесь для записи О-символикой, то это научный подход. Я ж ни разу не сказал, что особенности доступа к памяти и прочие нюансы «железа» не нужно учитывать на практике. Напротив, зная их Вы сумеете обоснованно подобрать как наиболее подходящую идеализированную структуру, так и конкретный способ ее программной реализации. Но вот так «поправляя» теорию Вы теряете те идеи и, следовательно, те результаты, которые теория дает. Неужели такая псевдонаучность того стоит?
Вы действительно считаете, что от статьи Тьюринга и описания его машины не было никакого толку?
Тогда из f(s)=O(g(s)) следует, что найдется такое положительное число A, что для всех s справедливо |f(s)|<A|g(s)|.
Вернее написать не "следует, что", а "по определению означает, что".
Термину o («o»-малое) соответствует определение
Не понимаю, что Вы имеете ввиду под фразой «подпирает с двух сторон». f(x) = O(g(x)) обозначает именно ограниченность сверху на некотором односторонне ограниченном интервале. Для ограниченности снизу обычно используют символ
у вас легко получилось, что O(1) = O(N). Для o() это верно, а для O() — нет.
Для О большого это тоже верно (с учетом того, что на самом деле это не равенство, а включение — но ведь это и для о малого так). Загляните в любой учебник матанализа.
Нельзя утверждать, что один алгоритм эффективнее другого на основании простого сопоставления их O-оценок. Такое утверждение всегда требует пояснений.
Нет, можно. Да, в общем случае, но вполне себе можно.
Другой вопрос — про ограниченный набор данных, специфические задачи и прочую конкретику. Но это уже не просто «один алгоритм эффективнее другого».
Нет, можно. Да, в общем случае, но вполне себе можно.
Дьявол кроется в деталях. В данном случае реализация алгоритма влияет на пресловутую константу в О-нотации. Поэтому нужно делать прототипы, производить измерения.
В данном случае реализация алгоритма влияет на пресловутую константу в О-нотации.
Первое, О-нотация исключает константы.
Второе, без констант два алгоритма одного класса будут одинаковы в Big-O, и простое сопоставление ни к чему не приведёт.
Первое, О-нотация исключает константы.
Смотрите, что написано в первой картинке.
Второе, без констант два алгоритма одного класса будут одинаковы в Big-O, и простое сопоставление ни к чему не приведёт.
Тогда как вы можете утверждать:
Да, в общем случае, но вполне себе можно.
Если мы да же не может утверждать, что быстрая сортировка эффективней сортировки слиянием. Или же сортировка 5 элементов пузырьком не эффективней быстрой сортировки?
Смотрите, что написано в первой картинке.Бред написан в первой картинке.
Если мы да же не может утверждать, что быстрая сортировка эффективней сортировки слиянием.Эти сортировки одного класса и в рамках Big-O они равны.
Я могу утверждать, что в общем случае быстрая сортировка быстрее пузырьковой, так как они разного класса.
Или же сортировка 5 элементов пузырьком не эффективней быстрой сортировки?Вы же даже процитировали меня, где я пишу «в общем случае». Разве сортировка 5 элементов — это общий случай?
В частных случаях Big-O может не давать ответа на вопрос, какой алгоритм лучше, тут нужны измерения. Но Big-O говорит о том, что мало смысла проводить сравнения с, например, пузырьковой сортировкой по умолчанию.
Нет, можно. Да, в общем случае, но вполне себе можно.
Нельзя. Самым простым примером в данном случае будут алгоритмы умножение матриц. Алгоритм Штрассена имеет оценку в O (n^2.81), а новый алгоритм Копперсмита — Винограда имеет оценку в O(n^2.3727).
Но на практике используется алгоритм Штрассена или его модификация из-за того, что алгоритм Копперсмита — Винограда дает прирост только на безумно больших матрицах. Привет от спрятанной константы.
Нельзя утверждать, что один алгоритм эффективнее другого на основании простого сопоставления их O-оценок.А не о применимости в реальной жизни. И я уточнил, что это «в общем случае». Вы второй человек который пишет в ответ про реальную жизнь.
В реальной жизни очень много переменных, которые придётся учитывать и сделать это точно слишком сложно (если вообще возможно), проще измерять. По измерениям, на реальных матрицах эффективнее алгоритм Штрассена? Используйте его. Но это не значит что он сразу стал эффективнее, напротив.
Во-вторых, на мой взгляд, асимптотическая сложность — это главный (и если мы говорим об аналитике, то единственный) критерий вычислительной эффективности алгоритма. Следовательно, алгоритм с лучшей асимптотикой будет эффективнее.
как Вам указали выше, вы не сможете сделать различие между алгоритмами с одинаковой O-асимптотикой.На уровне анализа — не сможете, конечно. Эта разница проявится только во время измерений. И результаты могут вас удивить.
А какой смысл вы вкладываете в слова "общий случай"? Если он на самом деле общий, то он должен включать все частные. А у вас что-то странное получается.
И вот в общем случае алгоритм с лучшей асимптотикой эффективнее.
Ваш вывод
Нельзя утверждать, что один алгоритм эффективнее другого на основании простого сопоставления их O-оценок.на мой взгляд, неверен.
Один алгоритм может быть эффективнее на ограниченном наборе значений n. Но это как сравнивать O(n) и O(log n). Можно найти пару конкретных вариантов, когда O(n) будет быстрее, но это не делает сам алгоритм эффективнее.
Человек, который, как у вас в примере, имеет именно такой случай и конкретные задачи должен это понимать.
PS. Кстати, на ограниченном наборе значений, как вы сами ловко подметили, у неё O(1), так что асимптотика теряет свой смысл.
Повторюсь, Вы просто подменяете понятия, называя «эффективностью алгоритма» его «асимптотическую сложность», в то время как это понятие включает в себя в том числе и поведение вычислимой функции на наборах данных конечной и даже конкретно фиксированной размерности.
Из O(1) следует только ограниченность, но не следует, что невозможно подобрать мажорирующую функцию, которая будет точнее описывать поведение исследуемой функции.А зачем вообще, по-вашему, подбирать мажорирующую функцию, если у нас уже есть исследуемая? Какой в этом смысл?
Повторюсь, Вы просто подменяете понятия, называя «эффективностью алгоритма» его «асимптотическую сложность», в то время как это понятие включает в себя в том числе и поведение вычислимой функции на наборах данных конечной и даже конкретно фиксированной размерности.Пожалуйста, приведите определение понятия «эффективность алгоритма», чтобы впредь избежать подмены, в которой вы меня обвиняете. Учитывая, что в статье определения нет, то со ссылкой на литературу. Вполне возможно, что мы под эффективностью алгоритма понимаем разные вещи.
Вы задали интересный вопрос, мне показалось, что он достоин очень подробного ответа.
Самое, наверное, общее и неформальное определение сложности (временной) — зависимость времени выполнения алгоритма от входных данных. Но поскольку время есть понятие растяжимое, то его формализовывают. Это возможно только в контексте некоторой модели вычислений. Например, если в качестве отправной точки взять определение, даваемое тезисом Черча-Тьюринга и строгую модель вычислений без типизации, то можно определить понятие сложности таким образом:
Пусть T — некоторое конечное множество атомарных вычислимых частичных операций, называемых элементарными, определенных над термами языка U. Пусть также задана функция
1.
2. Если s есть суперпозиция функций
3. Определим примитивную рекурсию (рекурсию по одному аргументу) относительно базы
Тогда если s есть примитивная рекурсия с базой
4. Если s есть минимизация (по последнему аргументу) относительно k-го аргумента функции f, то есть
5. Если s(a) не определена, то
Надеюсь, выше написанное не привело Вас в ужас. Потому что фактически здесь не написано ничего кроме очевидного: под сложностью мы понимает взвешенную сумму всех выполненных над заданным набором данных элементарных операций, сложность которых мы можем указать априори. Определив способ построения алгоритма из этих операций — например, как здесь путем указания минимально достаточного количества способов их комбинирования — мы имеем возможность конструктивно определить функцию сложности. Также очевидно, что такое определение столь же точно, сколь и бесполезно: для определения сложности алгоритма нужно знать количество операций, требуемых для обработки любого допустимого набора данных. Поэтому для практического анализа пытаются упростить себе жизнь, рассматривая не поведение алгоритма на множестве допустимых аргументов, а зависимость количества операций от некоторых простых характеристик этих самых аргументов. Самой общей, обезличенной и, наверное, самой удобной такой характеристикой является размерность входных данных, и тогда в рассмотрение вводится функция зависимости количества требуемых операций от размерности. Вполне понятно, что даже при таком упрощении построить подобную зависимость бывает весьма сложно и даже если это удастся, то просто в силу имевшей место подмены она даст лишь приближенное понятие о том, как в действительности изменяется поведение алгоритма при разных наборах данных.
Поэтому любая оценка O(f(N)), где под N понимают размерность данных, не является достаточной и дающей хоть сколь нибудь полное описание поведения алгоритма характеристикой.
Далее, любой достаточно сложный алгоритм имеет в своей структуре некоторое количество других алгоритмов, решающих определенные подзадачи. Их сложность также зависит от размерности данных и характер этой зависимости оказывает влияние на общую сложность. Цена решения, функции сложности некоторых подзадач могут оказаться по значению большими уже при малых размерностях, но медленно растущими — и это значит, что при достаточно больших размерностях их вклад в общую картину станет малым или даже незначительным, но на малых размерностях они могут почти полностью определять суммарную сложность. Поэтому имеет смысл рассматривать поведение функций сложности как во вполне конкретном интервале операционных размерностей, так и ее асимптотическое поведение — это позволяет увидеть, какие эффекты будут угасать, а какие наоборот окажутся доминирующими. Это фактически и есть асимптотическая оценка: мы подменяем функцию сложности такой, что начиная с определенного момента она точно не будет недооценивать реальную сложность алгоритма при условии, что все данные одинаковой размерности считаются неразличимыми, и при этом не будет уж совсем сильно нам врать. При этом совсем уж точная такая оценка и не нужна, ведь оцениваемая величина сама по себе лишь приблизительно описывает то, что нас в действительности интересует. Хотя бы по этому исходя только лишь из асимптотических оценок нельзя делать выводы в терминах «лучше — хуже» и «эффективнее — неэффективнее», для таких категорических утверждений они просто не дают достаточной информации.
Но давайте ответим на вопрос: Вас как специалиста-практика именно это интересует? Общая тенденция? Более вероятно, что Вы хотели бы узнать более точно относительно поведения вашего алгоритма в конкретном диапазоне размерностей. Более того, при таком приближении размерность уже перестает быть характеристикой, достаточной для предсказания типичного поведения программы — и тут Вы можете и должны рассматривать еще и другие аспекты. Вам становится важна устойчивость алгоритма, зависимость сложности от распределения входных данных, степень значимости тех или иных параметров и пр.
Один алгоритм может быть эффективнее на ограниченном наборе значений n.
При этом конкретный набор значений n будет зависеть от так называемых «деталей реализации» и конкретного железа, на котором он будет выполняться.
Поэтому если хотите сравнивать алгоритмы (абстрактные, а не конкретные реализации), то вы можете только сравнивать их оценки (О-большое, О-малое и др.).
под сложностью мы понимает взвешенную сумму всех выполненных над заданным набором данных элементарных операций, сложность которых мы можем указать априори
Вот в определении этих элементарных операций у нас и проблема. Вся статья про квадратный корень была про то, что принято рандомный доступ принято считать элементарной операцией, а он на самом деле гораздо сложнее. Хорошим теоретическим обоснованием было бы формальное представление структуры данных, включающей все уровни кэшей, памяти, свопа и тд. Со всеми подструктурами, алгоритмами, работающими на каждом уровне, пока мы не доберёмся до действительно элементарных операций. И тогда окажется, что мы таки зависим от железа, потому что кэши и алгоритмы выборок разные.
Да, sqrt(N) — совершенно среднепотолочная штука, да O нотация ничего не обещает, особенно когда её так неправильно используют, но пользоваться чем-то надо, а оно берёт и работает, не обещая.
Всем понятно, что мы зависим от железа. Все понимают, что линейная модель памяти, одноранговость элементарных операций и т.п. есть допущения, далеко не всегда выполняемые в реальной практике. Но построения моделей, которые будут учитывать все нюансы различных архитектур есть пустое расходывание времени теоретиков в тщетной попытке компенсировать ленность практиков. Потому что учет нюансов — это их, практиков задача, для решения которой им даны извилины в черепушке и профессиональные компетенции.
При программировании же не асимптотика нужна, а просто прогноз масштабируемости, и с sqrt он будет ближе к правде.
Какие применения O нотации в программировании?Нотация помогает по-разному:
С одной стороны, да, это выбор алгоритма. Среди множества можно быстро найти если не оптимальный, то набор лучших и дальше работать с ними.
С другой, это общее понимание подхода к программированию. Если понимать, что O(n^2) масштабируется плохо, и понимать что два вложенных for — это, как правило, как раз такой случай, то программисты, может быть, два раза подумают, прежде чем пихать всюду «for i for j».
Все эти деревья, связные списки и прочие хитрые придумки программистов сложно объяснить и понять без понимания Big-O. А начать ими пользоваться не только потому что «так надо»?
Иногда нахожу мнение, что Big-O это такая волшебная палочка: сверься с ней — и будешь счастлив. А иногда — что это бесполезная фигня с лекций олдскульщиков. На самом деле, эта нотация обладает главным полезным свойством — она простая, но позволяет моментально делать выводы о том или ином подходе, не вдаваясь в детали.
Если для вас факт перескакивания между уровнями памяти так критически важен — зачем вам вообще O-оценки, если за ними ничего, кроме Вашей персональной хотелки не стоит? Вы же в сущности хотите просто сказать, что если порции данных размера больше, чем некоторый и если в цикл скачет по памяти так, что каждый раз приходится обращаться к новой странице, то получится потеря в производительности, которой хотелось бы избежать. Так зачем делать вид, что за этим стоит какой-то строгий матаппарат?
Вы и так глядя в код и вывод профайлера поймете, где у Вас узкое место и как можно переформулировать алгоритм чтобы это компенсировать. Попробуйте вот так в инженерном деле взять, скажем, коэффициент Пуассона в расчете здания на прочность из головы — и вам оторвут всё отрывающееся.
Почему не нужно сваливать на неточность O-оценок свои проблемы