А я и не говорил, что O(log n) больше, чем O(n).
Я говорил, что на уровне «чистой» математики, собственно, само понятие «сложности» алгоритма — достаточно странная штука.
Для «чистого» математика выборка из массива чисел выглядит как «для всех X бОльших Y». А вот трудоемкость поиска этих самых X, бОльших этого самого Y — это уже вопрос скорее прикладной математики, применительно к конкретно имеющейся системе. Т.е. я больше о том, что в отрыве от конкретной модели, с которой мы работаем, налагающей свои вполне определенные ограничения, расчет трудоемкости и прочего, мягко говоря, не имеет смысла.
С точки зрения математика result = result0 + 4 = result1 * 18 = 24 * 5 — вполне себе нормальная цепочка. Для программиста инстанцирование промежуточных result'ов — боль и разразаривание ресурса.
Даже в случае сортировки, выборки и т.д. Если программист уверен в том, что размер списка значений не превысит, допустим, 4 элементов, оптимальный алгоритм сортировки — пузырек, оптимальный поиск — линейный перебор.Поэтому призывы «а давайте абстрагируемся от всех деталей и выпилим любую возможность в них углубиться, чтобы не вызывать соблазна» мне лично кажутся злом.
Т.е. вместо «uint_8», например, программисту предлагается разобрать «код проверки входных данных»? Гуммано…
В общем и целом статья строго философская, на тему «если бы слоны были бабочками». «Под капотом» у всего этого один фиг процессор с таки адресами памяти и набором примитивных операций. Вся «иммутабельность» и т.д. и т.п. — абстракция. При этом, в том виде, что предложен в статье, абстракция не имеет под собой основы и нарочь оторвана от реальности. Это все просто мат. теория.
Собственно, поиск по красно-черному дереву не имеет никакого математического обоснования. С точки зрения чистой математики поиск в дереве имеет бОльшую линейную сложность, чем элементарный перебор в лоб. Отсюда и проблема. В статье — красиво. На практике — это «горизонт», который, как мы помним, «удаляется по мере приближения».
Ну и, чтобы два раза не «вставать», движение Open Source держится не только и не столько на «признании, уважении и первенстве», сколько на простой невозможности некоторых людей не писать код. Скольких контрибюторов ядра Линукс вы знаете? Я — ни одного, кроме самого Линуса. О какой популярности тут может идти речь, если о них не знает никто, кроме тех, кто с ними же работает?
И даже тут «признание, уважение и первенство», таки имеет место быть. Просто признание не со стороны «ширнармасс», а конкретно со стороны «уважаемого человека Линуса», например. Признание от коллег и т.д. и т.п. Конечно, мировая слава не всех манит, но признание от людей, которых человек сам уважает (что важно), значит, причем значит многое.
Я говорил, что на уровне «чистой» математики, собственно, само понятие «сложности» алгоритма — достаточно странная штука.
Для «чистого» математика выборка из массива чисел выглядит как «для всех X бОльших Y». А вот трудоемкость поиска этих самых X, бОльших этого самого Y — это уже вопрос скорее прикладной математики, применительно к конкретно имеющейся системе. Т.е. я больше о том, что в отрыве от конкретной модели, с которой мы работаем, налагающей свои вполне определенные ограничения, расчет трудоемкости и прочего, мягко говоря, не имеет смысла.
С точки зрения математика result = result0 + 4 = result1 * 18 = 24 * 5 — вполне себе нормальная цепочка. Для программиста инстанцирование промежуточных result'ов — боль и разразаривание ресурса.
Даже в случае сортировки, выборки и т.д. Если программист уверен в том, что размер списка значений не превысит, допустим, 4 элементов, оптимальный алгоритм сортировки — пузырек, оптимальный поиск — линейный перебор.Поэтому призывы «а давайте абстрагируемся от всех деталей и выпилим любую возможность в них углубиться, чтобы не вызывать соблазна» мне лично кажутся злом.
В общем и целом статья строго философская, на тему «если бы слоны были бабочками». «Под капотом» у всего этого один фиг процессор с таки адресами памяти и набором примитивных операций. Вся «иммутабельность» и т.д. и т.п. — абстракция. При этом, в том виде, что предложен в статье, абстракция не имеет под собой основы и нарочь оторвана от реальности. Это все просто мат. теория.
Собственно, поиск по красно-черному дереву не имеет никакого математического обоснования. С точки зрения чистой математики поиск в дереве имеет бОльшую линейную сложность, чем элементарный перебор в лоб. Отсюда и проблема. В статье — красиво. На практике — это «горизонт», который, как мы помним, «удаляется по мере приближения».
И даже тут «признание, уважение и первенство», таки имеет место быть. Просто признание не со стороны «ширнармасс», а конкретно со стороны «уважаемого человека Линуса», например. Признание от коллег и т.д. и т.п. Конечно, мировая слава не всех манит, но признание от людей, которых человек сам уважает (что важно), значит, причем значит многое.