Кажется, «По статистике карты памяти Kingston являются самыми подделываемыми в мире. Мы обязательно расскажем, как не попасться на удочку мошенников.» — приоритетная статья :-)
Это не костыль.
Математика, как и все другие точные науки, соответствует критерию Поппера и имеет (на сегодняшний взгляд) бесконечные перспективы развития.
Ну так на вашем примере «2n+5 против 3n+6» это и действительно лучше, начиная от 1 до ∞.
Мы ведь не рассматриваем 0 количество данных? Или отрицательную длину массива?
Так что корректность соблюдается.
Конечно, можно было бы добавить, что _обычно_ берётся наивысшая степень полинома, а остальные _обычно_ отбрасываются. Но для больших чисел это само по себе сработает.
А так, да, я видел записи навроде вашей «O(2n+5)» у нормальных лекторов. Так что запись валидна.
Я прекрасно вижу, что семантически фраза означает «когда сложность алгоритма равна O(f(n)), то...» (и далее описываются свойства длительности от n с уже принятой договорённостью «сложность=О»), что фактически означает «Примем сложность равной О. Тогда...»
Я прекрасно понимаю, что такое О.
Я прекрасно понимаю, что такое количество элементарных операций.
Я прекрасно отдаю себе отчёт в том, что в первом приближении, равно как и для прикладного программирования в большинстве случаев полезнее объяснять и понимать O как число элементарных операций алгоритма, нежели академически доказывать равенство О какой-нибудь Гамма-функции Эйлера (и да, я в курсе, что это расширение факториала).
Тем более, что в программировании нет других критериев и способов подгонять длительность под какие-либо континуальные функции, кроме как посчитать количество операций.
Именно поэтому я объяснял молодому спрашивающему, что О большое это примерно количество операций алгоритма.
И да, я знаю, что прикладному математику нужно более строго определение. Но спрашивающий — не математик и математиком скорее всего уже не будет.
«Временная сложность алгоритма (в худшем случае) — это функция от размера входных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.»
Ещё раз: «равная максимальному количеству элементарных операций».
Таким образом, сложность вычислений пропорциональна количеству элементарных операций.
Так что, коллеги, реплики по поводу математической безграмотности моего объяснения кое-кто поторопился. Моё пояснение хоть и упрощено, но наглядно и достоверно показывает что означает O.
Указанные «неидеальные комментарии» ничего внятного не проясняют, кроме как жестами показывают «ого-го как сложно!..»
O большое — количество операций для завершения алгоритма. Число платформенно независимое.
Скажем, если вы тратите 1мс на операцию на своей архитектуре, то на сортировку десяти миллионов элементов массива алгоритмом O(N) вы затратите 10000000*0.001 секунд, алгоритмом O(logN) порядка 16*0.001 секунд.
При лидерстве следующий коллектив будет учиться у ведущего.
Автор не имеет в виду производственное программирование, когда вся терминология «проводки», «документы», «синхронизация», «роль», «консистентность» уже выработались и выпендриваться незачем.
Автор имеет в виду, что мы, программируя «обычные» бизнес-системы, уже идём в кем-то проторенной колее за теми, кто изобрёл эти названия.
Он подводит к мысли, что творя что-то новое, нужно обязательно снять с себя ограничения поиска ранее существовавших терминов.
А так же я его слышу как призывающего побольше создавать нового, чтобы отвоевать «право давать название» в индустрии.
Ну, статья либо цитирует Тайсона, либо перекликается с ним. www.youtube.com/watch?v=bIKjZDBpKik#t=1320
Это то, что он называет «право давать название» как индикатор лидерства.
Однако посыл «коллективы должны формировать свой языковой код для обслуживания своего прорыва» интересен. Постараюсь учесть.
«Хабр не для политики».
2 января сего года ходил.
Моё мнение:
1) Тема ролика прекрасна
2) Текст перевода прекрасен
3) Голос диктора неплох
И, главное, почему я это пишу:
3) Интонации диктора мёртвые. Вопросительная интонация совпадает с утвердительной. К тому же интонация не русская.
Математика, как и все другие точные науки, соответствует критерию Поппера и имеет (на сегодняшний взгляд) бесконечные перспективы развития.
Colobot
Ceebot
dBase/Clipper/FoxPro издревле изолируют прикладника от таких сложностей.
Да хоть какой частью тела юзатель будет биться о клавиатуру — по клавише «OK» программист получит что заказывал без вникания в акробатику.
Но автором (или таки переводчиком?) совершён едва ли не полный список расстрельных статей русского языка. Это печалит.
www.umopit.ru/jokes/Russian.htm
Мы ведь не рассматриваем 0 количество данных? Или отрицательную длину массива?
Так что корректность соблюдается.
Конечно, можно было бы добавить, что _обычно_ берётся наивысшая степень полинома, а остальные _обычно_ отбрасываются. Но для больших чисел это само по себе сработает.
А так, да, я видел записи навроде вашей «O(2n+5)» у нормальных лекторов. Так что запись валидна.
Я прекрасно понимаю, что такое О.
Я прекрасно понимаю, что такое количество элементарных операций.
Я прекрасно отдаю себе отчёт в том, что в первом приближении, равно как и для прикладного программирования в большинстве случаев полезнее объяснять и понимать O как число элементарных операций алгоритма, нежели академически доказывать равенство О какой-нибудь Гамма-функции Эйлера (и да, я в курсе, что это расширение факториала).
Тем более, что в программировании нет других критериев и способов подгонять длительность под какие-либо континуальные функции, кроме как посчитать количество операций.
Именно поэтому я объяснял молодому спрашивающему, что О большое это примерно количество операций алгоритма.
И да, я знаю, что прикладному математику нужно более строго определение. Но спрашивающий — не математик и математиком скорее всего уже не будет.
ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое
Читаем: «В частности: фраза «сложность алгоритма есть O(f(n))» означает, что...»
Смотрим, что такое «вычислительная сложность». Оп-па:
ru.wikipedia.org/wiki/Вычислительная_сложность
«Временная сложность алгоритма (в худшем случае) — это функция от размера входных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.»
Ещё раз: «равная максимальному количеству элементарных операций».
Таким образом, сложность вычислений пропорциональна количеству элементарных операций.
Так что, коллеги, реплики по поводу математической безграмотности моего объяснения кое-кто поторопился. Моё пояснение хоть и упрощено, но наглядно и достоверно показывает что означает O.
Указанные «неидеальные комментарии» ничего внятного не проясняют, кроме как жестами показывают «ого-го как сложно!..»
Если вам проще накидать минусов, чем помочь спрашивающему яснее, чем сделал я — давайте, ещё накидывайте. Так держать!
«Гики всех стран — разъединяйтесь через презрение!»
Скажем, если вы тратите 1мс на операцию на своей архитектуре, то на сортировку десяти миллионов элементов массива алгоритмом O(N) вы затратите 10000000*0.001 секунд, алгоритмом O(logN) порядка 16*0.001 секунд.
Подробнее --> в википедию.
И сам изобретал то, что плохо учил.
Это тоже мысль автора: «учите историю».
Но тут хотя бы термины знакомые.
Автор не имеет в виду производственное программирование, когда вся терминология «проводки», «документы», «синхронизация», «роль», «консистентность» уже выработались и выпендриваться незачем.
Автор имеет в виду, что мы, программируя «обычные» бизнес-системы, уже идём в кем-то проторенной колее за теми, кто изобрёл эти названия.
Он подводит к мысли, что творя что-то новое, нужно обязательно снять с себя ограничения поиска ранее существовавших терминов.
А так же я его слышу как призывающего побольше создавать нового, чтобы отвоевать «право давать название» в индустрии.
www.youtube.com/watch?v=bIKjZDBpKik#t=1320
Это то, что он называет «право давать название» как индикатор лидерства.
Однако посыл «коллективы должны формировать свой языковой код для обслуживания своего прорыва» интересен. Постараюсь учесть.