Привет всем, добро пожаловать в раздел о сокращении Big O. В первой частиЧитать полностью »
Рубрика «big o»
Big O нотация в Swift (часть 2 — Сокращение)
2022-11-27 в 10:18, admin, рубрики: big o, swift, АлгоритмыBig O нотация в Swift
2022-01-14 в 19:58, admin, рубрики: big o, swift, Алгоритмы, разработка под iOS, структуры данныхЧто такое Big O нотация?
Обозначение Big O нотация (или просто Big O) — это способ оценки относительной производительности структуры данных или алгоритма, обычно по двум осям: времени и пространству.
Доминирующие операции
Способ, которым мы определяем Big O алгоритмов, заключается в том, чтобы посмотреть на худшую производительность в его доминирующих операциях.
Постоянное время - O(1)
func constantTime(_ n: Int) -> Int {
let result = n * n
return result
}Почему не нужно сваливать на неточность O-оценок свои проблемы
2016-09-15 в 1:10, admin, рубрики: big o, cpu, ram, Алгоритмы, математика, о большое, ОЗУ, память, Программирование, процессор
На написание данного поста меня подвигла недавняя публикация этого и вот этого переводов, в которых авторы в интеллигентной форме выражают свое недовольство по поводу того, как O-оценки вычислительной сложности классических, казалось бы, алгоритмов вступили в диссонанс с их практическим опытом разработки. Основным предметом критики послужила модель памяти, в рамках которой эти оценки были получены — она, де, не учитывает особенности иерархической организации по принципу быстродействия, которая имеет место быть в современных вычислительных системах. От чего и произрастают все последующие неприятности. И судя по наблюдаемой реакции благодарных читателей, авторы далеко не одиноки в своем негодовании и желании «наехать» на классиков с их О-большими. Так возможно, действительно стоит отправить на свалку истории выкладки дядек в белых халатах, сделанные ими для ламповых тугодумающих и пышащих жаром машин, и дать дорогу молодым амбициозным моделям, более точно отражающим анатомию современного «железа»?
Миф о RAM и O(1)
2016-09-07 в 9:20, admin, рубрики: big o, cpu, ram, Алгоритмы, высокая производительность, математика, о большое, ОЗУ, память, Программирование, процессор, метки: big o, о большое
Городская библиотека Стокгольма. Фото minotauria.
В этой статье я хочу рассказать о том, что оценивать время обращения к памяти как O(1) — это очень плохая идея, и вместо этого мы должны использовать O(√N). Вначале мы рассмотрим практическую сторону вопроса, потом математическую, на основе теоретической физики, а потом рассмотрим последствия и выводы.
Введение
Если вы изучали информатику и анализ алгоритмической сложности, то знаете, что проход по связному списку это O(N), двоичный поиск это O(log(N)), а поиск элемента в хеш-таблице это O(1). Что, если я скажу вам, что все это неправда? Что, если проход по связному списку на самом деле O(N√N), а поиск в хеш-таблице это O(√N)?
Не верите? Я вас сейчас буду убеждать. Я покажу, что доступ к памяти это не O(1), а O(√N). Этот результат справедлив и в теории, и на практике. Давайте начнем с практики.
Измеряем
Давайте сначала определимся с определениями. Нотация “О” большое применима ко многим вещам, от использования памяти до запущенных инструкций. В рамках этой статьи мы O(f(N)) будет означать, что f(N) — это верхняя граница (худший случай) по времени, которое необходимо для получения доступа к N байтов памяти (или, соответственно, N одинаковых по размеру элементов). Я использую Big O для анализа времени, но не операций, и это важно. Мы увидим, что центральный процессор подолгу ждет медленную память. Лично меня не волнует, что делает процессор пока ждет. Меня волнует лишь время, как долго выполняется та или иная задача, поэтому я ограничиваюсь определением выше.Читать полностью »