Почему не нужно сваливать на неточность O-оценок свои проблемы

    На написание данного поста меня подвигла недавняя публикация этого и вот этого переводов, в которых авторы в интеллигентной форме выражают свое недовольство по поводу того, как O-оценки вычислительной сложности классических, казалось бы, алгоритмов вступили в диссонанс с их практическим опытом разработки. Основным предметом критики послужила модель памяти, в рамках которой эти оценки были получены — она, де, не учитывает особенности иерархической организации по принципу быстродействия, которая имеет место быть в современных вычислительных системах. От чего и произрастают все последующие неприятности. И судя по наблюдаемой реакции благодарных читателей, авторы далеко не одиноки в своем негодовании и желании «наехать» на классиков с их О-большими. Так возможно, действительно стоит отправить на свалку истории выкладки дядек в белых халатах, сделанные ими для ламповых тугодумающих и пышащих жаром машин, и дать дорогу молодым амбициозным моделям, более точно отражающим анатомию современного «железа»?

    А ты учел константу в О-большом?

    Давайте разбираться

    По ходу текста я буду ссылаться на вторую публикацию и некоторые комментарии к ней. Тронуло за живое. Но для начала давайте точно условимся что под чем понимается по ходу данного текста.

    Введем определение. Пусть и — две вещественные функции, определенные на множестве . Тогда запись означает, что найдется такое положительное число , что для всех справедливо . Такое обозначение называют -нотацией, а O называют символом Бахмана, либо просто "О-большим".

    Из этого определения сразу имеется несколько следствий:

    1. Если для всех имеет место , то из " следует, что . В частности, имеем, что умножение на константу не меняет O-оценку.

    Проще говоря, при умножении O-выражения на константу символ Бахмана эту константу «съедает». Это означает, что знак равенства в выражении, включающем в себя O-оценку, нельзя интерпретировать как классическое «равенство» значений и к таким выражениям нельзя применять математические операции без дополнительных уточнений. В противном случае мы бы получили странные вещи по типу следующей: . Это следствие произвольности константы, которая «прячется» за символом Бахмана.

    2. Если ограничена на , то есть существует такое число , что для всех выполняется , то .

    Переводя с математического на русский и взяв для простоты в качестве конечный интервал числовой прямой, имеем следующее: если функция на заданном интервале не уходит в бесконечность, то самое бессмысленное, что можно о ней еще сказать — это то, что ей соответствует O(1). Это совершенно ничего нового не говорит о ее поведении.

    Угадай мою сложность
    Голубая линия это O(√N).

    Вернемся к случаю оценки сложности алгоритма и посмотрим на картинку, приводимую автором цитируемой публикации. Наблюдая рост времени выполнения, делается вывод о несостоятельности оценки O(1). Но интервал, на котором анализируется поведение программы, конечен. Значит по факту утверждается, что оценка O(1) на нем плоха.

    Чтож… спасибо, Кэп.

    Более того, дальше делается попытка угадать! мажорирующую функцию просто по виду кривой, дескать, «гля как похоже». Не проводя никакого анализа самого алгоритма с учетом тех особенностей, на которых пытаются акцентировать внимание и не вводя никакой модели памяти! А почему, собственно, там корень квадратный, а не кубический? Или не логарифм какой-нибудь залетный? Ну, право слово, предложили бы хоть пару-тройку вариантов, зачем же сразу «внимание, правильный ответ»?

    Здесь стоит оговориться. Я, естественно, не веду к неверности выводов о том, что при переходе к «более далекому» от процессора накопителю время доступа падает. Но время получения порции данных при произвольном доступе к памяти даже на самом медленном уровне иерархии есть величина постоянная или хотя бы ограниченная. Из чего и следует оценка O(1). А если она не ограниченная и зависит от размерности данных — значит доступ к памяти не произвольный. Ну тупо по определению. Давайте не забывать, что мы имеет дело с идеализированными алгоритмическими конструкциями. Поэтому когда говорится, что «дальше за HDD пойдут датацентры»… Господа, ну какой же это произвольный доступ, какие массивы и хэш-таблицы? Это называется мухлёж под столом: вы втихаря меняете условия задачи, приводите ответ к предыдущей и кричите: «Ахтунг! Неправильно-то как!». У меня это вызывает приступ тяжелого недоумения. Ведь если за словом array, vector или <какой-то-тип>* ваш компилятор скрывает, скажем, кусок распределенной по узлам кластера памяти — то это по структуре может быть что угодно, но не массив в терминах книг Вирта и Кнута, и применять к ним написанные в этих книгах результаты формального анализа в высшей степени бестолковая идея. И не меньшая шизофрения — на полном серьезе говорить об общности оценки, придуманной глядя на график с результатами произвольного теста.

    Ошибочность приводимого суждения заключается в том, что O-оценка сложности делается на основании эксперимента. Чтобы это подчеркнуть, введем еще одно «свойство» O-нотации, применимое к оценкам алгоритмической сложности:

    3. O-оценка может быть получена только из анализа структуры алгоритма, но не из результатов эксперимента. По результатам эксперимента можно получить статистические оценки, экспертные оценки, прикидочные оценки и, наконец, инженерное и эстетическое удовольствие — но не асимптотические оценки.

    Последнее является следствием того, что сам смысл подобных оценок — это получить представление о поведении алгоритма при достаточно больших размерностях данных, причем насколько больших обычно не уточняется. Это не единственная и далеко не всегда главная, но представляющая интерес характеристика алгоритма. Во времена Дейкстры и Хоара достаточно большими можно было считать порядки размерности 3-6, в наше время 10-100 (по моим не претендующим на глубину анализа оценкам). Иными словами, ставя вопрос о получении асимптотических оценок функции сложности алгоритма, удобно модифицировать определение O-нотации таким образом:

    Пусть . Тогда означает, что существуют взаимно независимые положительные числа A и n, такие что для всех выполняется .

    То есть при анализе алгоритмической сложности мы фактически рассматриваем мажоранты функции сложности на всех ограниченных слева и не ограниченных справа интервалах. Значит таких О-оценок может быть указано сколь угодно много и все такие оценки могут оказаться практически полезными. Некоторые из них будут точными для малых N, но быстро уходить в бесконечность. Другие будут расти медленно, но станут справедливы начиная с такого N, до которого нам на наших убогих компьютерах как пешком до Луны. Так что если допустить, что за оценкой времени доступа к памяти скрыт какой-либо структурный анализ, то эту оценку вполне можно было бы использовать в определенном диапазоне размерностей, но даже тогда она бы не отменила верность оценки O(1).

    Классический пример некорректного сравнения асимптотических оценок — алгоритмы умножения квадратных матриц. Если делать выбор между алгоритмами только на основании сравнения оценок, то берем алгоритм Уильямс и не паримся. Можно лишь пожелать творческих успехов решившему применить его к матрицам характерных для инженерных задач размерностей. Но с другой стороны, мы знаем, что начиная с некоторой размерности задачи алгоритм Штрассена и различные его модификации будут работать быстрее тривиального, и это дает нам пространство для маневра при выборе подходов к решению задачи.

    Как из умности получаются глупости


    Грешить на неточность O-оценок — значит полностью не понимать смысл этих оценок, и если это так — то никто не заставляет их использовать. Вполне можно и зачастую оправдано предпочитать им статистические оценки, полученные в результате тестов на специфических именно для вашей области наборах данных. Неграмотное использование такого тонкого инструмента, как асимптотический анализ, приводит к перегибам и вообще удивительным штукам. Например, используя O-нотацию, можно ""«доказать»"" несостоятельность идеи параллельного программирования.

    Допустим, что наш алгоритм, которому скармливается порция данных размерности N и который при последовательном выполнении имеет сложность , легко и непринужденно разбивается на те же N независимых и для простоты одинаковых по вычислительной и временной сложности частей. Получаем, что сложность каждой такой части есть . Пусть у нас есть M независимых вычислителей. Тогда общая сложность выполнения параллельного алгоритма есть ничто иное как . Получилось, что асимптотическая оценка сложности алгоритма в результате даже идеальной параллелизации на конечное число процессов не меняется. Но внимательный читатель заметил, что изменилась «спрятанная» константа, которую схомячил символ Бахмана. То есть делать из подобного анализа какие-то общие выводы относительно самой идеи параллелизации по меньшей мере глупо. Но возможна и другая крайность — забыть, что количество процессоров конечно и на основании бесконечного ресурса параллелизма утверждать, что оценка «параллельной версии алгоритма» есть O(1).

    Подведем итоги


    В качестве вывода можно предоставить следующие подкупающие новизной утверждения:

    • Нельзя утверждать, что один алгоритм эффективнее другого на основании простого сопоставления их O-оценок. Такое утверждение всегда требует пояснений.

    • Нельзя из результатов замеров производительности делать вывод о правильности или неправильности таких оценок — спрятанная константа обычно неизвестна и может быть достаточно большой.

    • Можно (а иногда нужно) рассуждать об алгоритмах и структурах данных вообще не используя такие оценки. Для этого достаточно просто сказать, какие конкретно их свойства вас интересуют.

    • Но лучше все-таки принимать конкретные инженерные решения, учитывая в том числе и такие характеристики употребляемых алгоритмов.

    За утверждением о неточности, неправильности или непрактичности асимптотических оценок часто скрыто нежелание провести нормальный предварительный анализ поставленной проблемы и попытка опираться на название, но не суть тех абстракций, с которыми имеют дело. Говоря об асимптотической сложности алгоритма, грамотный специалист понимает, что речь идет об идеализированных конструкциях, держит в уме степень корректности проецирования их на реальное «железо» и никогда, от слова «вообще», не принимает инженерных решений опираясь только и исключительно на нее. O-оценки более полезны при разработке новых алгоритмов и поиске принципиальных решений сложных задач и намного менее полезны при написании и отладке конкретных программ под конкретное железо. Но если вы их неправильно интерпретировали и получили совсем не то, что обещало вам ваше понимание прочитанного в умных книжках — согласитесь, это не проблема тех, кто эти оценки доказательно получил.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 71

      –15
      Ну да, в умных книжках абстракный исполнитель в вакууме, а не реальное железо. И для него эти оценки работают. Но смысла от них как от машины тьюринга — одна теория. На практике необходима другая система оценки, оценивающая современную архитектуру. И понимание O большого никак не отменяет необходимости ввести другую систему оценки. Тоже теоретической, тоже модельной, но уже заточенной под наше железо.

      Ваше предложение оценивать производительность алгоритмов постфактум, тестами — порочно. Откуда вы будете знать какие вообще алгоритмы реализовывать, чтобы потестить?
        +20
        Для написания программ под x86 пользы от машины Тьюринга и впрямь никакой, она не для этого и делалась. А вот для доказательства алгоритмической неразрешимости некоторых задач она очень даже кстати, а сие телодвижение позволит при попадании на такого рода задачу не биться головой об стену в поисках решения, а направить свои ментальные усилия в направлении поиска других подходов к вставшей инженерной проблеме.

        Ваше замечание ровно о том, что я написал в конце. Вы хотите иметь не математический инструмент, а дельфийского оракула: Вы к нему с задачей — он Вам алгоритм, ну или хотя бы «посмотри сюда, сравни это — и будет тебе счастье», как в справочнике слесаря-сантехника. Не бывает так, нет здесь серебряной пули и нормальный теоретический анализ алгоритма требует подходить к нему больше, чем с одного бока. Не можете провести такой анализ — используйте экспериментальные методы исследования. Не можете или не хотите делать ни того, ни другого — пользуйтесь эмпирическими рекомендациями в руководствах по языкам программирования. Можете выполнить и то, и другое — вообще золотой специалист.
          0
          Вы ошибаетесь, я разумеется, хочу иметь инструмент, а не волшебную палочку. Математический инструмент, в рамках которого удобно обсуждать производительность программы. Такой показатель, который позволяет классифицировать производительность алгоритмов, который легко вычислить для простого алгоритма, и к которому легко редуцировать составленный из более простых алгоритмов.

          > Для написания программ под x86 пользы от машины Тьюринга и впрямь никакой, она не для этого и делалась. А вот для доказательства алгоритмической неразрешимости некоторых задач она очень даже кстати,

          А вы не задумывались, зачем появилась в информатике О-большая нотация, когда уже была абстракция машины Тьюринга? Ведь последнего достаточно для рассуждений о вычислимости? Как оказалось, абстракция машины Тьюринга совершенно не подходит для оценки производительности алгоритмов на актуальном железе. И вот ввели новый инструмент, чисто для того, чтобы найти адекватный способ измерения производительности, подходящий для реального железа того периода.

          Время идёт, новое железо уже совсем не похоже на старое. Понемногу, в деталях, оно трансформировалось в нечто, нарушающее все принципы машины фон-Неймана. Пора, соответственно, и математический аппарат подтянуть. Добавить новую, актуальную абстракцию. А старую модель оставить истории и теории, там же, где сейчас находится машина Тьюринга. Кстати, последнее время тьюринг-полноту принято показывать не приведением к оригинальной машине, а вычислением rule 110.

          И задача теоретиков от computer science предоставить для практиков новую абстракцию, удобную к современному применению. Вы ведь не называете жалкими недоучками тех программистов, которые опираются (опирались когда это было актуально) на классические алгоритмы и их оценки?
            +10
            То, что Вы описали как раз вполне соответствует описанию волшебной палочки. Вы хотите иметь возможность запросто получать простые ответы на сложные вопросы.

            Так получилось, что я эти вопросы знаю. Машина Тьюринга в принципе не предназначена для ответа на вопросы о вычислительной сложности, она предназначалась для получения строгого ответа на вопросы «что есть алгоритм?» и какой «класс задач можно решить чисто механически?». О-нотация появилась совсем не в связи с алгоритмами, а с изучением введенных Пуанкаре асимптотических рядов. Просто так получилось, что при анализе вычислительной сложности эта нотация обычно оказывается достаточно удобной. Она позволяет упростить анализ, исключая по мере надобности лишние множители. Это вообще никак не связано с реальным железом, только лишь с удобством вычислений. Так что не надо валить все в кучу.
            Машины Тьюринга и архитектура фон Неймана вещи мало связанные и нарушение принципов второй никак не сказывается на первой. Чем стара эта модель, тем что не удовлетворяет вашим потребностям как специалиста-практика? Еще раз повторюсь, ее не для того придумывали. И свою историческую задачу она, вообще говоря выполнила. Для ответа на другие вопросы придумывались другие модели и приемы.

            Но вы пытаетесь перевернуть все с ног на голову, ставя вопрос так, что вам нужен новый метод оценки старых алгоритмов. В самом основании этих «старых» алгоритмов лежали базовые упрощения действительности типа линейной модели памяти, и анализ их асимптотического поведения шел рука об руку с процессом их формулировки. Этот процесс не работает так, что вот мы что-то придумали — и давай его анализировать методами асимптотического анализа. Вас не устраивает, как старые алгоритмы ложатся на новое железо? Так садитесь и придумывайте новые. Но зачем же ставить CS-никам не свойственные им задачи потому, что такая их формулировка кажется Вам правильной?
              –1
              > Вы хотите иметь возможность запросто получать простые ответы на сложные вопросы.

              Именно. А для чего ещё математика нужна?

              > О-нотация появилась совсем не в связи с алгоритмами

              Ну да. А теория категорий появилась гораздо раньше хаскеля. Но притащили её в CS как раз любители функционального программирования, приспособив для своих нужд уже имеющуюся математическую абстракцию.

              > Чем стара эта модель, тем что не удовлетворяет вашим потребностям как специалиста-практика?

              Не учитывает локальность памяти.

              > Так садитесь и придумывайте новые.

              Там и без меня справляются. Уже лет десять как написали сортировку для видеокарт, например.

              Проблема в том, что пора обновлять базовые абстракции и лексику. Язык ведь частично определяет мышление. Если нет термина, то соответствующее явление попадает в слепое пятно. Потому статьи, что вы цитировали, так полезны — заставляют обратить внимание на объективное явление. Дальше уже каждый по мере разумения корректирует свои представления. Говорит «а ведь и правда, есть такое дело», начинает по-новому смотреть на мир. Ну и предлагает остальным прозревшим разработать общую терминологию и общие решения для описанных проблем. Это как паттерны проектирования — полезны тем, что структурируют мысли и дают программистам общий язык.
                +6
                Математика дает ответы, когда и если поставлены правильные вопросы. Предлагаете свою постановку — Ваше право. Но на результат не обижайтесь.

                Ну так и я об этом, О-нотация была привнесена как удобное средство описания и анализа. Реальное железо тут совсем не при чем, как и машины Тьюринга.

                И не должна, потому что с точки зрения алгоритмической полноты это свойство не имеет значение.

                А до прочтения этих статей факт того, что память разделена на несколько уровней, был от Вас сокрыт? Просто это не тот вопрос, который требует какого-то перелопачивания теории, поскольку те самые асимптотические оценки остаются, вообще говоря, справедливыми. Авторы процитированных мной статей банально не понимают, что такое асимптотические оценки, пытаются рассуждать о них в привычных для себя категориях и приходят к (первый) выводу, что, пардон, ну их нафиг, лучше доверять тестам, чутью и мануалам на библиотеки языка, и (второй) к какой-то нелепой, высосанной из пальца оценке с наукообразным ее обоснованием. И тут проблема в том, что никто никого не вводил в заблуждения — сами заблудились, воспринимая такие оценки не тем, чем они на самом деле являются, а как нечто монолитное.
                Да, фактическое поведение временной сложности изменилось, стало более сложным — но учитывать такого рода нюансы в рамках общего подхода, пытаться на каждый случай делать модели и формулировать подходы — дело гиблое, тут больше на руку сыграет тот же статистический анализ. Такие проблемы не в ведении ученых — они для них пусты, а в зоне Вашей ответственности: оцените потребность программы в памяти, особенности естественной организации данных, характер ожидаемых обращений, а если в состоянии — особенности целевой архитектуры и алгоритмов управления памятью операционной системы. После этого можно прикинуть подходящую оценку сложности того или иного алгоритма, поднять имеющиеся рекомендации к применению функций выбранной библиотеки и принять конкретное инженерное решение. Если Вы хотите, чтобы эту работу сделали за Вас яйцеголовые, предоставив некоторую общую модель — слишком многого хотите.

                А базовые абстракции и так обновляются, а точнее пополняются. Появляются модели вычислителей с распределенной памятью, grid-архитектурой и пр. В рамках этих моделей как раз и разрабатываются новые алгоритмы и методы анализа. Насчет языков соглашусь, такая проблема есть, хотя и не стоит пока очень уж остро.
                  –3
                  > А до прочтения этих статей факт того, что память разделена на несколько уровней, был от Вас сокрыт?

                  Нет, конечно. Но я не задумывался во всей полноте о последствиях. Привык полагаться на асимптотические оценки.

                  > Да, фактическое поведение временной сложности изменилось, стало более сложным

                  Ага. Вместе с этим изменилась целевая функция оптимизации. Что предполагает необходимость замены некоторых классических алгоритмов на другие. И на стандартизацию работы с кешами. Необходимо уже как-то более осознанно подходить к кешированию памяти, доставать её из-под капота. Потому что, пока она пребывает исключительно под капотом компиляторов и шедулеров, её трудно учитывать.

                  > Тут больше на руку сыграет тот же статистический анализ.

                  Как вы будете статистически анализировать _алгоритмы_?
                    +3
                    Я вам не скажу за всю Одессу… но вот лично по моему опыту если уж встала реальная потребность в оптимизации какого-либо критичного участка кода, то такие вопросы, как сложность наиболее часто выполняемой в коде операции для различных подходящих под нужды структур, локализация выделяемых участков памяти, возможность выделения памяти в стеке вместо кучи, способ организации коллекций в стандартных библиотеках и прочие детали производства сами всплывают в памяти с пометкой «важно». Иногда приходится вообще отказываться от стандартных решений в плане организации данных. Мной это воспринимается как часть нормальной инженерной работы, которую куда легче и лучше выполнить ручками, нежели рыться в поисках свежей публикации с более адекватной моей задаче моделью вычислительной системы. Ну не учтете вы все нюансы в абстрактной модели.

                    Вы, видимо, хотите поймать меня за руку на неточности определения. Уточнюсь. Можно использовать результаты статистического анализа программной реализации алгоритма. Или нескольких реализаций. Да хоть всех когда-либо написанных на всех известных человечеству архитектурах, если это позволит принять Вам обоснованное решение по выбору и алгоритма, и его конкретного программного воплощения.
                      +1
                      Проблема собственно в том, что их надо предварительно реализовать. Если задача действительно важная, вы, конечно, найдёте время реализовать десять разных алгоритмов и прогнать их через тесты. Вопрос заключается в другом, как отобрать эти десять перспективных алгоритмов для реализации и тестирования? По каким параметрам?
                        0
                        Провести предварительную приблизительную оценку. О-оценка — первый эшелон. Вы знаете характерную размерность данных и, вероятно, только на основании этого сможете сузить круг кандидатов. Далее, у Вас есть описание алгоритмов и думаю, что Вы в состоянии оценить, насколько их особенности сыграют в плюс или в минус в Вашем случае. Потом можете посмотреть документацию на основные реализации выбранных алгоритмов, там часто есть замечания, которые стоит принять к сведению. И если у Вас осталось несколько перспективных кандидатов — лопату в руки и проводим эксперимент. Замеряем то, что для Вас критично — расход памяти, среднее время для характерных размерностей, разброс результатов при характерном же распределении данных и т.п.
                  0
                  То что вы ищете называется cache-oblivious model: https://en.wikipedia.org/wiki/Cache-oblivious_algorithm
                  Эта модель, придуманная ещё в середине девяностых, несколько более сложна, чем традиционная RAM, поэтому под неё разработано меньше алгоритмов. Так получается, я полагаю, потому что при решении ещё нерешённой задачи люди сначала предпочитают всесторонне рассмотреть её в близкой (и часто практической), но более простой обычной RAM, а уже потом смотрят на кэш/внешнюю память/параллелизм.
                +1
                Ну не была О-нотация заточена под конкретное железо то никогда. Она была сделано же для того что бы можно было посмотреть как поведет себя алгоритм при изменениях количества и качества входных данных. И с этим неплохо справляется.
                И задача теоретиков от computer science предоставить для практиков новую абстракцию, удобную к современному применению

                С чего вдруг теоретики должны под конкретную платформу предоставлять новые нотации? А универсальной нотации тут очевидно быть не может. Автор совершенно прав — мозгами думать просто надо а не на О-нотацию все валить.
                  0
                  О-нотация (...) была сделана же для того что бы можно было посмотреть как поведет себя алгоритм...

                  Создатели о-символики и не помышляли об алгоритмах.

                    0
                    Спасибо. Действительно, как то не подумал что ее применение гораздо шире чем только анализ алгоритмов.
                  0
                  O-оценка вообще не имеет отношения к железу. Можно сказать, что она считает количество шагов алгоритма. Если в вашей модели вычислений время выполнения одного шага ограничено константой, то O-анализ дает еще и асимптотическую оценку времени.

                  В модели многоуровнего доступа к памяти используются те же самые O-оценки, просто с другим описанием того, что такое один шаг, лучше отражающим структуру кэшей. Почитайте, например про модель кэш-памяти, используемую при анализе таких алгоритмов. Она давным давно разработана теоретиками computer science, просто редко кому нужна и довольно непроста.
                  0
                  Если не для тех, кто пишет программы, то для кого проводились исследования и строилась теория вычислительной сложности? «Глас народа — ...». Оценки сложности всегда даются по отношению к некоторой конкретной вычислительной модели, и тот факт, что народ негодует по поводу применяемой RAM модели с доступом к памяти за ограниченное константой количество ходов машины имеет на самом деле не только расхождение с реальными машинами но и некоторые противоречия с теорией передачи информации. Вот вам задачка:
                  Пусть имеются конечный набор типов идеальных логических элементов («транзисторов» или схем, реализующих более сложные функции). Можно ли построить, пусть даже из бесконечного числа таких элементов, универсальную вычислительную машину с бесконечным адресным пространством и равномерно ограниченным временем доступа ко всем ячейкам памяти (конечного объема), если все логические элементы тратят ровно один ход на выполнения реализуемой ими функции, а сигнал между ними передается мгновенно?

                  Заметьте, что я снял все ограничения физического или экономического характера, тем не менее, бьюсь об заклад, что смогу перенумеровать ячейки памяти любой удовлетворяющей условиям машины так, что доступ к ним из начального состояния будет ограничен снизу по количеству шагов логарифмом их номера в моей нумерации.

                    0
                    Вот только теорию информации сюда приплетать не надо, ее задачи ортогональны задачам теории алгоритмов и вычислительной сложности. И если мы с Вами начнем еще и ее обсуждать в контексте программистской практики, то сильно рискуем заблудиться в деталях. Вы ж не будите в самом деле в процессе написания прикладной программы с сетевым обменом под винду еще и учитывать особенности передачи сигнала по беспроводному каналу?

                    Про необходимость ограниченности времени доступа к памяти некоторой константой нигде не говорилось, это бы противоречило допущению бесконечности памяти. Говорилось о том, что вводя такие понятия, как массив или линейный список обычно явно или неявно фиксируются базовые допущения, потом постулируются основные свойства и далее вводятся и параллельно оценивается сложность основных операций. Это значит, что говоря слово «массив» вы уже предполагаете одинаковое время доступа к произвольному элементу и только тогда имеете право опираться на полученные для массива оценки сложности. В случае иерархической организации памяти такие допущения приемлемы, если в среднем большая часть операций проводится на одном из уровней. Если же Вы понимаете, что у вас характер распределения данных и обращения к ним таков, что такие эффекты окажут существенное влияние на общий итог — ну так учтите это, рассмотрите такую организацию данных как другую структуру, свойства которой точнее отражают состояние дел. Так нет же, Вы хотите, чтобы кто-то за вас рассмотрел «массив» в устраивающем именно Вас смысле этого слова. Поймите, это вообще не задача тех, кто занимается исследованием алгоритмов и теорией вычислений, учет нюансов целевой архитектуры — это задача в первую очередь разработчиков операционных систем и компиляторов. Это они озадачены тем, как наиболее эффективно спроецировать алгоритмы, сформулированные в терминах удобной для использования и исследования модели, на реальное железо. Если Вам не нравятся их решения — берите в руки спецификацию на процессор и делайте всё сами. Вот если действующая модель принципиально не ложится на конкретный набор железа хоть сколь-нибудь эффективно как, например, в случае гетерогенных распределенных вычислительных систем — вот тут в игру вступают дядьки в очках на носу и с мелом в руках и вводят в рассмотрение новые модели и методы. А вопросы, на которых Вы пытаетесь заострить внимание, вполне в компетенции инженеров (должны быть, по крайней мере) и для теоретиков большого интереса не представляют.
                      +1
                      А все-таки время доступа к элементам массива из n элементов в оперативке зависит от n? Sergey_Kovalenko утверждает, что это логарифм, а не константа.
                        0
                        Говоря слово «массив» Вы уже предполагаете, что не зависит. Такое определение у слова «массив». Я ж писал об этом в статье: то, что понимает компилятор и следом за ним Вы под словами array, vector и т.д. далеко не всегда, а скорее уж почти никогда, соответствует каноническому определению. Пользуясь теоретическими оценками Вы должны это понимать. И если пропасть между этими «теоретическими» и «практическими» одноименными конструкциями становится ну уж совсем большой — так перестаньте пользоваться написанными в книжках ответами и проведите более детальный анализ, введя в рассмотрение способ организации данных, более точно описывающий способ их обработки в ЦП. Для этого же в институтах и учат всяким примудростям матанализа и теории алгоритмов.
                          +2
                          Я настаиваю на несколько другой идеи:
                          Пусть имеется процессор и оперативная память размера N, соединенная с ним шиной. Невозможно обработать запрос на доступ к ячейке памяти в среднем быстрее чем за полином от логарифма N срабатываний элементарных логических элементов, из которых набрана шина. Если дела внутри процессора намного хуже, то эта оговорка не имеет значения, но в случае специализированных вычислений может иметь смысл так сегментировано организовать память, чтобы в каждом сегменте адресов было поменьше.
                            0
                            N — размер оперативки или размер выделенной под структуру данных памяти?
                              0
                              Принципиально можно так сконструировать шину, чтобы (упрощенно) адрес распадался на длинный адрес сегмента и короткий адрес ячейки в сегменте, при этом на машинном уровне шине сообщалось, будут ли ближайшие запросы попадать в один и тот же сегмент. В этой ситуации программы можно так писать, чтобы N было размером структуры данных, размещаемой внутри оперативной памяти. В плохо сделанных компьютерах N будет размером оперативной памяти.
                                0
                                Но ведь тогда получается, что в плохо сделанных компьютерах полином от log(N) — это константа и сложность доступа к ячейке оказывается O(1), а в хорошо сделанных время доступа всё равно оказывается ограниченной сверху величиной и значит снова O(1).
                                  –1
                                  Давайте ваше рассуждение возьмем за пример: берем любой алгоритм любой сложности, скажем O(e^n). Все равно максимальное значение n — это размер оперативки, или там размера харда, то есть сложность ограничена константой, поэтому она O(1).
                                    0
                                    Вы неверно трактуете мои рассуждения. Я ведь не просто так переспросил, что понимается под N. Если N есть размер оперативки, то это величина внешняя по отношению к алгоритму, входит в оценку его сложности как константа и не влияет на асимптотическую оценку. Если же N — размерность структуры, то (если я правильно понял вышеописанную идею) сложность обращения к ячейке оказывается в зависимости от количества окружающих его запросов к соседним ячейкам. Но даже в самом худшем случае, когда запросы совершенно не локализованы, имеется ограничение сверху на время доступа к ячейке, не зависящее от размера структуры. Из этого и следует оценка O(1). И еще раз повторюсь, если время доступа не ограничено, то называть структуру массивом нет никакого смысла и необходимо для теоретического рассмотрения таких способов организации данных в памяти вводить другие идеализированные конструкции.
                                      0
                                      Алгоритмы все таки предполагают, что они будут реализованы на подходящей для размера задачи машине, а не на первой попавшейся. Может быть, когда машина выбрана, размер оперативной памяти уже внешняя константа, однако я предполагаю, что вам будет удобно решать большие задачи на машинах с большим размером памяти, а маленькие, из моих слов, — будут быстрее считаться на маленьких ЭВМ. Именно в момент выбора подходящей плохой машины логарифм и выстрелит.
                                        –2
                                        И вот мы подобрались к сути недопонимания. Алгоритм — это математическое понятие, оно не может быть завязано на выбор конкретной машины. Алгоритм решает математическую задачу и как следствие не может и не должен в своей базовой формулировке учитывать все нюансы физического исполнителя, иначе не удастся построить ни одного нормального алгоритма. Именно поэтому у машины Тьюринга бесконечная лента.
                                        Ваш «логарифм», который «выстрелит» — это придумка, поправка, которой Вы надеетесь компенсировать разницу между своим собственным восприятием теории и наблюдаемой практикой. Вводя такие поправки Вы в первую голову себя вводите в заблуждения, думая, что раз Вы все еще пользуетесь для записи О-символикой, то это научный подход. Я ж ни разу не сказал, что особенности доступа к памяти и прочие нюансы «железа» не нужно учитывать на практике. Напротив, зная их Вы сумеете обоснованно подобрать как наиболее подходящую идеализированную структуру, так и конкретный способ ее программной реализации. Но вот так «поправляя» теорию Вы теряете те идеи и, следовательно, те результаты, которые теория дает. Неужели такая псевдонаучность того стоит?
                    +1

                    Вы действительно считаете, что от статьи Тьюринга и описания его машины не было никакого толку?

                    +5
                    это очень дельная статья
                      0
                      Тогда из f(s)=O(g(s)) следует, что найдется такое положительное число A, что для всех s справедливо |f(s)|<A|g(s)|.

                      Вернее написать не "следует, что", а "по определению означает, что".

                        0
                        Согласен, спасибо за правку
                          0
                          В определение закралась небольшая ошибочка. Дело в том, что приведенное определение соответствует термину o() а не O(). Поэтому у вас легко получилось, что O(1) = O(N). Для o() это верно, а для O() — нет. O() «подпирает» функцию с двух сторон, поэтому речь идет об асимптотически одинаковом поведении функций. Поэтому они и используются в анализе алгоритмов.
                            +2
                            Это где у меня получилось, что О(1) = О(N)? Я ж вроде как четко написал, что асимптотические оценки проверять на равенство нельзя, потому что такое «равенство» по определению не может быть симметричным. Но при этом возможно одновременно, что f(x) = O(1) и f(x) = O(N).

                            Термину o («o»-малое) соответствует определение

                            Не понимаю, что Вы имеете ввиду под фразой «подпирает с двух сторон». f(x) = O(g(x)) обозначает именно ограниченность сверху на некотором односторонне ограниченном интервале. Для ограниченности снизу обычно используют символ , определение то же самое, что и у О-большого, только знак неравенства меняется на противоположный. А если и , то пишут
                              0
                              Да, вы правы. Перепутал с Тетой.
                              +2
                              у вас легко получилось, что O(1) = O(N). Для o() это верно, а для O() — нет.
                              Для О большого это тоже верно (с учетом того, что на самом деле это не равенство, а включение — но ведь это и для о малого так). Загляните в любой учебник матанализа.
                            +2
                            Я могу ошибаться, но на критикуемом рисунке вообще не дана функция, удовлетворяющая критерию Бахмана, поскольку она явно меньше целевой функции в некоторых интервалах области опеределения и, скорее всего, за ее пределами. Там дана скорее аппроксимирующая функция, которая никак оценкой сверху не является.
                              +3
                              Формально можно подобрать константу и функция станет строго больше экспериментальной кривой. Но в силу конечности промежутка это верно для совершенно любой монотонно неубывающей функции. Так что не ошибаетесь, на рисунке показан полный бред.
                                0
                                Для убывающих тоже — главное, чтобы на этом промежутке она была больше некоторого положительного числа была, чтобы можно было её на нём поднять сколь угодно высоко домножением на константу. Вообще, неважно, какая это функция — главное, чтобы на требующемся промежутке все её значения были больше некоторого x>0. И какой график — тоже неважно, лишь бы ограничен сверху был.
                                  0
                                  Вообще достаточно того, чтобы функция была всюду положительной, но это уже неважные для нашего вопроса детали.
                              0
                              Нельзя утверждать, что один алгоритм эффективнее другого на основании простого сопоставления их O-оценок. Такое утверждение всегда требует пояснений.

                              Нет, можно. Да, в общем случае, но вполне себе можно.

                              Другой вопрос — про ограниченный набор данных, специфические задачи и прочую конкретику. Но это уже не просто «один алгоритм эффективнее другого».
                                0
                                Нет, можно. Да, в общем случае, но вполне себе можно.

                                Дьявол кроется в деталях. В данном случае реализация алгоритма влияет на пресловутую константу в О-нотации. Поэтому нужно делать прототипы, производить измерения.

                                  0
                                  В данном случае реализация алгоритма влияет на пресловутую константу в О-нотации.


                                  Первое, О-нотация исключает константы.
                                  Второе, без констант два алгоритма одного класса будут одинаковы в Big-O, и простое сопоставление ни к чему не приведёт.
                                    0
                                    Первое, О-нотация исключает константы.

                                    Смотрите, что написано в первой картинке.


                                    Второе, без констант два алгоритма одного класса будут одинаковы в Big-O, и простое сопоставление ни к чему не приведёт.

                                    Тогда как вы можете утверждать:


                                    Да, в общем случае, но вполне себе можно.

                                    Если мы да же не может утверждать, что быстрая сортировка эффективней сортировки слиянием. Или же сортировка 5 элементов пузырьком не эффективней быстрой сортировки?

                                      0
                                      Смотрите, что написано в первой картинке.
                                      Бред написан в первой картинке.
                                      Если мы да же не может утверждать, что быстрая сортировка эффективней сортировки слиянием.
                                      Эти сортировки одного класса и в рамках Big-O они равны.

                                      Я могу утверждать, что в общем случае быстрая сортировка быстрее пузырьковой, так как они разного класса.
                                      Или же сортировка 5 элементов пузырьком не эффективней быстрой сортировки?
                                      Вы же даже процитировали меня, где я пишу «в общем случае». Разве сортировка 5 элементов — это общий случай?

                                      В частных случаях Big-O может не давать ответа на вопрос, какой алгоритм лучше, тут нужны измерения. Но Big-O говорит о том, что мало смысла проводить сравнения с, например, пузырьковой сортировкой по умолчанию.
                                  0
                                  Нет, можно. Да, в общем случае, но вполне себе можно.

                                  Нельзя. Самым простым примером в данном случае будут алгоритмы умножение матриц. Алгоритм Штрассена имеет оценку в O (n^2.81), а новый алгоритм Копперсмита — Винограда имеет оценку в O(n^2.3727).


                                  Но на практике используется алгоритм Штрассена или его модификация из-за того, что алгоритм Копперсмита — Винограда дает прирост только на безумно больших матрицах. Привет от спрятанной константы.

                                    0
                                    Изначально речь о том, что
                                    Нельзя утверждать, что один алгоритм эффективнее другого на основании простого сопоставления их O-оценок.
                                    А не о применимости в реальной жизни. И я уточнил, что это «в общем случае». Вы второй человек который пишет в ответ про реальную жизнь.

                                    В реальной жизни очень много переменных, которые придётся учитывать и сделать это точно слишком сложно (если вообще возможно), проще измерять. По измерениям, на реальных матрицах эффективнее алгоритм Штрассена? Используйте его. Но это не значит что он сразу стал эффективнее, напротив.
                                      0
                                      Вы таким образом подменяете общее понятие «вычислительной эффективности» более узким «асимптотическая вычислительная сложность». Но тогда, как Вам указали выше, вы не сможете сделать различие между алгоритмами с одинаковой O-асимптотикой.
                                        0
                                        Во-первых, как я уже предложил ниже, давайте придём к общему пониманию понятия «вычислительной эффективности». Что вы понимали под ним в статье?

                                        Во-вторых, на мой взгляд, асимптотическая сложность — это главный (и если мы говорим об аналитике, то единственный) критерий вычислительной эффективности алгоритма. Следовательно, алгоритм с лучшей асимптотикой будет эффективнее.
                                        как Вам указали выше, вы не сможете сделать различие между алгоритмами с одинаковой O-асимптотикой.
                                        На уровне анализа — не сможете, конечно. Эта разница проявится только во время измерений. И результаты могут вас удивить.
                                        0

                                        А какой смысл вы вкладываете в слова "общий случай"? Если он на самом деле общий, то он должен включать все частные. А у вас что-то странное получается.

                                          0
                                          Да, общий случай — это такой случай, который включает все частные. То есть, и те матрицы, с которыми реально работают инженеры, и малюсенькие, и огромные, которые, возможно, никогда и не понадобятся. Или понадобятся через тысячи лет.

                                          И вот в общем случае алгоритм с лучшей асимптотикой эффективнее.
                                            0

                                            Так вот, если вы утверждаете, что некий алгоритм эффективнее другого в общем случае, то это значит, что он должен быть эффективнее во всех частных случаях.

                                              0
                                              Ну окей, имеется ввиду подавляющее большинство случаев.

                                              Иначе, один алгоритм не может быть эффективнее другого, так как всегда найдётся какой-нибудь частный случай, когда один алгоритм не хуже другого.
                                                0

                                                Да, конечно.

                                      0
                                      Перечитайте, пожалуйста, пример про алгоритмы перемножения матриц. Это не виртуальный, а вполне практически значимый пример.
                                        +1
                                        Конечно, реальный. И пример правильный. Неправильный только вывод.

                                        Ваш вывод
                                        Нельзя утверждать, что один алгоритм эффективнее другого на основании простого сопоставления их O-оценок.
                                        на мой взгляд, неверен.

                                        Один алгоритм может быть эффективнее на ограниченном наборе значений n. Но это как сравнивать O(n) и O(log n). Можно найти пару конкретных вариантов, когда O(n) будет быстрее, но это не делает сам алгоритм эффективнее.

                                        Человек, который, как у вас в примере, имеет именно такой случай и конкретные задачи должен это понимать.

                                        PS. Кстати, на ограниченном наборе значений, как вы сами ловко подметили, у неё O(1), так что асимптотика теряет свой смысл.
                                          0
                                          Нет, не теряет. Из O(1) следует только ограниченность, но не следует, что невозможно подобрать мажорирующую функцию, которая будет точнее описывать поведение исследуемой функции.

                                          Повторюсь, Вы просто подменяете понятия, называя «эффективностью алгоритма» его «асимптотическую сложность», в то время как это понятие включает в себя в том числе и поведение вычислимой функции на наборах данных конечной и даже конкретно фиксированной размерности.
                                            0
                                            Из O(1) следует только ограниченность, но не следует, что невозможно подобрать мажорирующую функцию, которая будет точнее описывать поведение исследуемой функции.
                                            А зачем вообще, по-вашему, подбирать мажорирующую функцию, если у нас уже есть исследуемая? Какой в этом смысл?
                                            Повторюсь, Вы просто подменяете понятия, называя «эффективностью алгоритма» его «асимптотическую сложность», в то время как это понятие включает в себя в том числе и поведение вычислимой функции на наборах данных конечной и даже конкретно фиксированной размерности.
                                            Пожалуйста, приведите определение понятия «эффективность алгоритма», чтобы впредь избежать подмены, в которой вы меня обвиняете. Учитывая, что в статье определения нет, то со ссылкой на литературу. Вполне возможно, что мы под эффективностью алгоритма понимаем разные вещи.
                                              +1
                                              А у Вас нет исследуемой. У Вас есть некоторые приближенные сведения о ее поведении.

                                              Вы задали интересный вопрос, мне показалось, что он достоин очень подробного ответа.

                                              Самое, наверное, общее и неформальное определение сложности (временной) — зависимость времени выполнения алгоритма от входных данных. Но поскольку время есть понятие растяжимое, то его формализовывают. Это возможно только в контексте некоторой модели вычислений. Например, если в качестве отправной точки взять определение, даваемое тезисом Черча-Тьюринга и строгую модель вычислений без типизации, то можно определить понятие сложности таким образом:

                                              Пусть T — некоторое конечное множество атомарных вычислимых частичных операций, называемых элементарными, определенных над термами языка U. Пусть также задана функция . Определим множества как замыкание T относительно операций суперпозиции, примитивной рекурсии и минимизации, и U* — как множество всех конечных последовательностей из элементов U (то есть замыкание U относительно операции декартового произведения). Элементы U* будем обозначать . Назовем сложностью вычислимой функции относительно аргумента значение функции L(s, a), определенной следующим образом:

                                              1. .

                                              2. Если s есть суперпозиция функций относительно функции , то есть , то .

                                              3. Определим примитивную рекурсию (рекурсию по одному аргументу) относительно базы , функции перехода h и функции приращения t как функцию f, такую, что:



                                              Тогда если s есть примитивная рекурсия с базой , функцией перехода h и функцией шага по аргументу t, то

                                              . Это сложность попадания в базу.



                                              4. Если s есть минимизация (по последнему аргументу) относительно k-го аргумента функции f, то есть , — итерирующая функция, — начальное значение, то . Здесь G есть замыкание G0 множества относительно операции композиции, в пересечении с множеством функций, определенных на U и имеющих результатом a (очевидно, такое множество либо пусто, либо содержит единственную функцию g); .

                                              5. Если s(a) не определена, то .

                                              Надеюсь, выше написанное не привело Вас в ужас. Потому что фактически здесь не написано ничего кроме очевидного: под сложностью мы понимает взвешенную сумму всех выполненных над заданным набором данных элементарных операций, сложность которых мы можем указать априори. Определив способ построения алгоритма из этих операций — например, как здесь путем указания минимально достаточного количества способов их комбинирования — мы имеем возможность конструктивно определить функцию сложности. Также очевидно, что такое определение столь же точно, сколь и бесполезно: для определения сложности алгоритма нужно знать количество операций, требуемых для обработки любого допустимого набора данных. Поэтому для практического анализа пытаются упростить себе жизнь, рассматривая не поведение алгоритма на множестве допустимых аргументов, а зависимость количества операций от некоторых простых характеристик этих самых аргументов. Самой общей, обезличенной и, наверное, самой удобной такой характеристикой является размерность входных данных, и тогда в рассмотрение вводится функция зависимости количества требуемых операций от размерности. Вполне понятно, что даже при таком упрощении построить подобную зависимость бывает весьма сложно и даже если это удастся, то просто в силу имевшей место подмены она даст лишь приближенное понятие о том, как в действительности изменяется поведение алгоритма при разных наборах данных.

                                              Поэтому любая оценка O(f(N)), где под N понимают размерность данных, не является достаточной и дающей хоть сколь нибудь полное описание поведения алгоритма характеристикой.

                                              Далее, любой достаточно сложный алгоритм имеет в своей структуре некоторое количество других алгоритмов, решающих определенные подзадачи. Их сложность также зависит от размерности данных и характер этой зависимости оказывает влияние на общую сложность. Цена решения, функции сложности некоторых подзадач могут оказаться по значению большими уже при малых размерностях, но медленно растущими — и это значит, что при достаточно больших размерностях их вклад в общую картину станет малым или даже незначительным, но на малых размерностях они могут почти полностью определять суммарную сложность. Поэтому имеет смысл рассматривать поведение функций сложности как во вполне конкретном интервале операционных размерностей, так и ее асимптотическое поведение — это позволяет увидеть, какие эффекты будут угасать, а какие наоборот окажутся доминирующими. Это фактически и есть асимптотическая оценка: мы подменяем функцию сложности такой, что начиная с определенного момента она точно не будет недооценивать реальную сложность алгоритма при условии, что все данные одинаковой размерности считаются неразличимыми, и при этом не будет уж совсем сильно нам врать. При этом совсем уж точная такая оценка и не нужна, ведь оцениваемая величина сама по себе лишь приблизительно описывает то, что нас в действительности интересует. Хотя бы по этому исходя только лишь из асимптотических оценок нельзя делать выводы в терминах «лучше — хуже» и «эффективнее — неэффективнее», для таких категорических утверждений они просто не дают достаточной информации.

                                              Но давайте ответим на вопрос: Вас как специалиста-практика именно это интересует? Общая тенденция? Более вероятно, что Вы хотели бы узнать более точно относительно поведения вашего алгоритма в конкретном диапазоне размерностей. Более того, при таком приближении размерность уже перестает быть характеристикой, достаточной для предсказания типичного поведения программы — и тут Вы можете и должны рассматривать еще и другие аспекты. Вам становится важна устойчивость алгоритма, зависимость сложности от распределения входных данных, степень значимости тех или иных параметров и пр.
                                            +1
                                            Один алгоритм может быть эффективнее на ограниченном наборе значений n.

                                            При этом конкретный набор значений n будет зависеть от так называемых «деталей реализации» и конкретного железа, на котором он будет выполняться.

                                            Поэтому если хотите сравнивать алгоритмы (абстрактные, а не конкретные реализации), то вы можете только сравнивать их оценки (О-большое, О-малое и др.).
                                              +1
                                              Да, совершенно верно.
                                                –1
                                                Нет, не верно. Дело не в железе, а в сложности структуры самих алгоритмов. Я там, выше, на вопрос коллеги простыню с пояснением накатал.
                                                  +2
                                                  под сложностью мы понимает взвешенную сумму всех выполненных над заданным набором данных элементарных операций, сложность которых мы можем указать априори

                                                  Вот в определении этих элементарных операций у нас и проблема. Вся статья про квадратный корень была про то, что принято рандомный доступ принято считать элементарной операцией, а он на самом деле гораздо сложнее. Хорошим теоретическим обоснованием было бы формальное представление структуры данных, включающей все уровни кэшей, памяти, свопа и тд. Со всеми подструктурами, алгоритмами, работающими на каждом уровне, пока мы не доберёмся до действительно элементарных операций. И тогда окажется, что мы таки зависим от железа, потому что кэши и алгоритмы выборок разные.
                                                  Да, sqrt(N) — совершенно среднепотолочная штука, да O нотация ничего не обещает, особенно когда её так неправильно используют, но пользоваться чем-то надо, а оно берёт и работает, не обещая.
                                                    0
                                                    В определении того, что есть элементарная операция всегда проблема. Но то, что Вы пытаетесь предложить — это разговоры в пользу бедных. Неужели Вы искренне полагаете, что те, кто на профессиональном уровне занимаются разработкой и анализом алгоритмов решения конкретных задач не имеют представления об архитектуре современного железа? Но модели такого рода, как Вы предлагаете, не создаются. И если Вы когда-нибудь что-нибудь моделировали, то должны понимать почему: от слишком сложной модели проку не больше, чем от слишком грубой. Можно ввести темень кромешную переменных, огромное количество структурных взаимосвязей, максимально приблизив модель к моделируемому объекту. Но такая модель не позволит Вам ответить ни на один из поставленных вопросов.
                                                    Всем понятно, что мы зависим от железа. Все понимают, что линейная модель памяти, одноранговость элементарных операций и т.п. есть допущения, далеко не всегда выполняемые в реальной практике. Но построения моделей, которые будут учитывать все нюансы различных архитектур есть пустое расходывание времени теоретиков в тщетной попытке компенсировать ленность практиков. Потому что учет нюансов — это их, практиков задача, для решения которой им даны извилины в черепушке и профессиональные компетенции.
                                          +8
                                          Вы конечно правы, теоретически. Но вот на практике знать об асимптотике без возможности проецировать на задачу бессмысленно. Какие применения O нотации в программировании? Отсечь на ранних этапах совсем невозможное (O(e^n) при заведомо известных n > 100500) и оценить масштабируемость работающего решения. И в большинстве случаев масштабируемость оценивается очень хорошо. Линейный поиск на вдвое большем массиве работает вдвое медленней. А перебор всех пар (O(n^2)) — в 4 раза медленней. И это действительно работает и этим активно пользуются. Предложение считать доступ к памяти как O(sqrt(n)) вместо O(1) — всего лишь способ учесть на практике иерархии кэшей, просто эвристика. В любом инженерном деле таких допущений множество, эврситики проще точной теории. У математиков всегда волосы дыбом встают от того, что вытворяют физики и тем более инженеры. «Так нельзя!», зато работает.
                                          При программировании же не асимптотика нужна, а просто прогноз масштабируемости, и с sqrt он будет ближе к правде.
                                            0
                                            Какие применения O нотации в программировании?
                                            Нотация помогает по-разному:

                                            С одной стороны, да, это выбор алгоритма. Среди множества можно быстро найти если не оптимальный, то набор лучших и дальше работать с ними.

                                            С другой, это общее понимание подхода к программированию. Если понимать, что O(n^2) масштабируется плохо, и понимать что два вложенных for — это, как правило, как раз такой случай, то программисты, может быть, два раза подумают, прежде чем пихать всюду «for i for j».

                                            Все эти деревья, связные списки и прочие хитрые придумки программистов сложно объяснить и понять без понимания Big-O. А начать ими пользоваться не только потому что «так надо»?

                                            Иногда нахожу мнение, что Big-O это такая волшебная палочка: сверься с ней — и будешь счастлив. А иногда — что это бесполезная фигня с лекций олдскульщиков. На самом деле, эта нотация обладает главным полезным свойством — она простая, но позволяет моментально делать выводы о том или ином подходе, не вдаваясь в детали.
                                              +1
                                              Простите конечно, но вот такое наукообразие меня раздражает. Это как сказать: у нас деталь неидеально круглой формы, по нормам не проходит, но давайте pi возьмем равным четырем — а инженерный расчет проведем как для круглой. Это же эвристическая оценка!
                                              Если для вас факт перескакивания между уровнями памяти так критически важен — зачем вам вообще O-оценки, если за ними ничего, кроме Вашей персональной хотелки не стоит? Вы же в сущности хотите просто сказать, что если порции данных размера больше, чем некоторый и если в цикл скачет по памяти так, что каждый раз приходится обращаться к новой странице, то получится потеря в производительности, которой хотелось бы избежать. Так зачем делать вид, что за этим стоит какой-то строгий матаппарат?
                                              Вы и так глядя в код и вывод профайлера поймете, где у Вас узкое место и как можно переформулировать алгоритм чтобы это компенсировать. Попробуйте вот так в инженерном деле взять, скажем, коэффициент Пуассона в расчете здания на прочность из головы — и вам оторвут всё отрывающееся.
                                              +2
                                              Сейчас мы тут наспоримся, а завтра 99% комментариев пойдут писать бизнес логику на джаве и еще год не вспомнят об O-нотации. Скриньте!
                                                +2
                                                В бизнес-логике это тоже работает. Недоодинэсники начинают велосипедить циклы там, где можно обойтись одним запросом и получить примерно 100кратный прирост производительности. При чем тут О-большое? Понимание этой нотации заставляет призадуматься о подходе к решению задач.
                                                  0
                                                  Кстати, о бизнес-логике. Подумалось внезапно, что бизнес-логика тоже бывает разной. В одной зеленой конторке бизнес-логика включает в себя, например, нелинейные задачи квадратичного программирования с нелинейными и невыпуклыми ограничениями — Солвер под такую стоит over 180килодолларов.
                                                  0
                                                  Большое спасибо за статью и радует ее положительный рейтинг. А то, увидев множество одобрительных комментариев в статье про память, я уж испугался, что на Хабре начинается эра Indiana Pi Bill, но нет — все в порядке, можно выдохнуть )
                                                    0
                                                    К сожалению, множится количество адептов «секты эмпирического причастия». Большинство из них (тех, кто мне попадался) оказываются не готовы дискутировать на тему архитектуры ЭВМ. Им сложно понять, что кэши процессора созданы для системы предсказания, которая сама решает, что там хранить, а не для прямого употребления пользователем / программой. Им сложно принять, что процессор решит сам, что там оставить, ведь это противоречит «аксиоме из квадратного корня». Им сложно принять, что процессор «додумался» после нескольких проходов по маленькому массиву скопировать весь этот массив в кэш, ожидая, что эта частая операция повторится вновь на синтетических сектантских тестах.

                                                  Only users with full accounts can post comments. Log in, please.