Как стать автором
Поиск
Написать публикацию
Обновить

Комментарии 24

Неожиданный взгяд на проблемы сложности алгоритмов.
Обычно оценивается алгоритм, потом только его реализация, котора зависит от железа/системы существенно.
Мне кажется корректно сравнивать реализации одного и того же алгоритма или различные алгоритмы.
Комментарий пока не оценивали0
Ответ правильный, но ваше решение неверно. Даже с эффективной ToBinaryString, ответ все равно будет O(nlog3(n)). Метод Remove работает за O(log(n)) сравнений, но каждое сравнение требует O(log(n)) операций, поскольку мы сравниваем строки длины O(log(n)). Прерывание сравнения на первом отличающемся символе не изменяет асимптотики (чем глубже мы в дереве, тем больше совпадающих символов).
Всего голосов 1: ↑1 и ↓0+1
Хм. Не заметил, что там HashSet, вместо TreeSet. Тогда не понятно как учитывать хэш-коллизии. Асимптотика может зависеть от хэш-функции.
Всего голосов 1: ↑1 и ↓0+1
Да, тут этот момент не очень корректен, вы правы. O-оценка подразумевает худший случай, но за сложность операций с HashSet мы взяли их сложность в среднем. Теоретически некорректно, но практически так всегда и делают :)
Комментарий пока не оценивали0

Хотя тут добавляются вполне конкретные числа — подряд. Для них то мы можем быть уверены в амортизированной сложности Add и Remove

Комментарий пока не оценивали0

А тут самое время заглянуть в документацию :)


This method is an O(1) operation. — HashSet.Remove() в .NET (https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.hashset-1.remove?view=netframework-4.7.1)

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. — HashSet в JDK (https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html)
Всего голосов 2: ↑2 и ↓0+2

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


Обидно, в этом месте допустил ошибку — и про гармонический ряд знал, и про расходимость, но с асимптотикой частичных сумм промахнулся (почему-то думал, что это O(n²)).


Вот про конкатенацию строк (и добавочный множитель из-за этого) — интересный момент, действительно, легко проморгать. Хотя это, наверное, больше вопрос к реализации и выбору контейнеров (например, меня, не очень знакомого с C# и Java, даже не сразу триггернуло в этом месте). Как верно заметили выше, можно (и нужно!) тогда копать ещё глубже, и решение становится всё менее очевидным.

Всего голосов 2: ↑2 и ↓0+2
Спасибо, поправил ссылку на правильную. Слишком плодовитый был этот Эйлер! :)
Всего голосов 1: ↑1 и ↓0+1
Вообще-то конкатенация строк плохо себя ведет в любом языке, не только в C# и Java. Просто потому что конкатенация по определению всегда создает новую строку — и тут уже неважно являются ли строки в языке изменяемыми.

Разве что в случае с Rust есть надежда что компилятор заметит что один из операндов более не используется и подберет более подходящую перегрузку — но для этого надо правильно проставить типы.
Комментарий пока не оценивали0
Вообще-то конкатенация строк плохо себя ведет в любом языке, не только в C# и Java. Просто потому что конкатенация по определению всегда создает новую строку — и тут уже неважно являются ли строки в языке изменяемыми.

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

Комментарий пока не оценивали0
Только random-access будет работать не за O(1), да? И при выводе строки констата вырастет порядочно.
Всего голосов 1: ↑1 и ↓0+1

В теории почти всё так (с упомянутыми оговорками про то, что O — оценка сверху). Но мы же на хабре, тут на слово верят только запустив код :) Я вот решил проверить. Была открыта IDEA, поэтому на Java. 


        double v = 10;
        double max = 5000000;
        double k = 1.1;

        while (v<max){
            long start = System.nanoTime();
            Set<String> set = compute((int) v);
            long elapsed = System.nanoTime() - start;
            System.out.print((int) v);
            System.out.print("\t");
            System.out.print(set.size());
            System.out.print("\t");
            System.out.print(elapsed);
            System.out.println();
            v = v * k;
        }

(Да, я знаю про JMH, да, я знаю что замер не самый удачный)
Ну так вот. Скопировал я результаты в Excel, поигрался. Попробовал найти асимптоту. Оно как бы и находится (у меня коэффициент elapsed/(n*log(n)^3)сходится примерно в 4.5), но погрешность от GC и прочих прелестей делает слабо отличимыми nlog(n)^3 от nlog(n)^2.


А если говорить про решето Эратосфена, то классический список оптимизаций примерно такой:


  1. Wheel optimization (в простейшем случае проверять только 6n+1, 6n-1 для чисел от 5)
  2. Конечно перейти к BitArray / BitSet, а скорее всего самим сделать их аналоги, чтобы перейти границу в maxInt. Это не только улучшит O-оценку, но и позволит на современных машинах легко считать в лоб (в пямяти) решето примерно до 2^37..2^40 (2^33 занимает 1 ГБ). На сладкое — не нужны хеши.
  3. В цикле for (int step = 2; step < n; step++) не надо идти до n. Достаточно до sqrt(n) (не считая, конечно, его в каждой итерации и аккуратно обработав пограничные случаи).
  4. Этот же цикл должен идти только по простым числам.
  5. Решето Эратосфена великолепно параллелится. Решето Аткина, кстати, параллелить сложнее. А еще в решете Аткина нужен flip которого нет в .NET BitArray (но мы же решили пилить свой класс)
  6. На десерт можно переписать toBinaryString() без рекурсии и с более эффективным построением строки.
Всего голосов 1: ↑1 и ↓0+1

UPD: dotnet тоже потыкал аналогично:


  1. Дотнет у меня в тесте слил. Я смотрел на текущем релизном core. JDK какой-то из свежих 1.8
  2. Картина та же — сходимость "как бы есть", но реально получается что-то между n*log(n)^3, n*log(n)^2, n*log(n)^2*log(log(n)) и прочими подобными вариациями. Если дать голые числа, то зависимость именно n*log(n)^3 там найти даже с подсказкой непросто.

(ИМХО) В данном конкретном случае знание оценки в O-нотации не сильно поможет тому, кто оптимизирует этот код:


  • Это "решето Эратосфена" не может просчитать и десяток миллионов тупо упираясь в память.
  • На алгоритмах "близких к линейным", т.е. все эти n*log(n) улучшение константного коэффициента даёт существенный эффект. И уж точно даже примитивная wheel optimization выиграет больше (в 3 раза от наивного обхода), чем переход от n*log(n)^3 в n*log(n)^2
  • Многие алгоритмы перебора или просеивания не имеют красивых и посчитанных O-оценок. Или имею, но именно O — худший случай и это какая-нибудь экспонента от полинома (привет переборщики :) ), но при применении хороших эвристик решение может быть найдено.
Всего голосов 2: ↑2 и ↓0+2

Регулярно наблюдаю на самом компетентном математическом форуме рунета очередные темы с предложениями новых авторских алгоритмов, асимптотически превосходящих лучшие существующие аналоги. Где регулярно авторов разочаровывают, что, например, сложение и умножение — это не О(1), а О(n). Вы конечно хитро спрятались за явными интами, но обычно асимптотическую сложность принято оценивать у абстрактного алгоритма без привязки к конкретным деталям реализации убогой конкатенации иммутабельных строк. В том же Хаскеле с его автовыводом типов при автоматическом расширении с интов до интеджеров асимптотика существенно изменится (при одном и том же коде!), но "честная" алгоритмическая останется какой и была. Другое дело, что вы не рассказываете про "честную", а ограничиваетесь кустарной-наколеночной, да еще языко-платформозависимой. Но при этом позиционируете себя как эксперта в этой области, и еще обучаете потенциальных авторов очередных супер-алгоритмов, о которых я писал в начале этого комментария.

Всего голосов 4: ↑0 и ↓4-4

Я учу инженеров оценке сложности с чисто прикладной целью. Учёных учат другие люди.

Всего голосов 3: ↑3 и ↓0+3
Если это для инженеров, то нужно считать битовые операции.
Всего голосов 1: ↑0 и ↓1-1
Но вот в чем проблема — мне вряд ли понадобится Haskell или запись алгоритма на бумажке, а вот на Java нужно писать каждый день.
Всего голосов 1: ↑1 и ↓0+1
хм, на сабжевом ресурсе как бы есть возможность входа через ВК, но по факту опять же предлагается регистрировать и придумывать пароль. Зачем так?
Комментарий пока не оценивали0
Я когда-то спрашивал xoposhiy об этом, причина оказалась довольно юмористическая. Среди пользователей ulearn.me много студентов, а университеты любят внезапно блокировать доступ к поддоменам vk.com из внутренней сети. Тогда студентам не только мемасики не посмотреть, но и курс не пройти. Поэтому сейчас ulearn.me предлагает задать пароль даже при входе через ВК, чтобы был резервный способ входа.
Комментарий пока не оценивали0
Рил ток. Заблокировали ВК прямо в середине семестра :(
Комментарий пока не оценивали0
Справедливости ради, остаётся недоказанной равносильность перехода от сложности алгоритма for-for-toBinaryString к произведению сложности вложенных циклов for-for и сложности метода toBinaryString, поскольку x в оценке O(log²(x)) метода зависит от состояния цикла.

Выше предлагается эмпирически способ подсчёта вычислительной сложности с засеканием времени. Ещё один альтернативный способ (без необходимости засекать время):
  1. Заменяем все операции на увеличение счётчика.
  2. Если количество операций может быть посчитано явно (без необходимости крутить цикл или рекурсию, то прибавляем сразу необходимое количество.
  3. Делаем для n разного порядка и подбираем подходящую асимптотику.
  4. Profit!
Всего голосов 3: ↑3 и ↓0+3
Про недоказанность ты заблуждаешься. Некоторых математических упражнений стоит доказательство этого перехода в терминах точной оценки Θ. Но в терминах верхней оценки О-большого всё доказывается тривиальным образом: заменяем X на большую величину N. Готово.
Всего голосов 1: ↑1 и ↓0+1
Смотря как посмотреть. Если строго формально, то да, вы правы. Но только с тем же успехом можно утверждать что удаление из хэшсета у нас O(n!). Не, ну а чё? Константа действительно растет не быстрее факториала. Только есть одна проблема — данный ответ, не смотря на свою абсолютную правильность, не несет абсолютно никакой пользы. Так что для практического использования важно брать не просто верхнюю оценку, а «близкую» верхнюю оценку. И вот здесь допустимость замены sum(2,n,log^2(x)) -> nlog^2(n) уже не так очевидна. (сорри, на знаю как красиво формулы писать сюда)
Комментарий пока не оценивали0
Да, мы можем заменить x на n и получить некоторую оценку, но мы не можем тривиальным образом утверждать из-за огрубления, что она будет точнее прочих предложенных:
Наиболее точный ответ на последний вопрос предлагалось выбрать из внушительного списка вариантов.
Всего голосов 1: ↑1 и ↓0+1
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr