Комментарии 15
Очень вводящий в заблуждение цветной график на рисунке. Зачастую на практике сравнительная эффективность алгоритмов определяется константной частью, при этом кривые не исходят из одной точки (0, 0), как показано на графике.
Хорошо было бы привести примеры для ловушек.
https://github.com/dinozavr2005/ios-library/tree/main/Алгоритмы/Arcade
накидал примеров, можно попробывать посмотреть и постараться разобраться что там происходит
Программисты на Свифте профильной литературы не читают и в школе институте не учатся?
Зачем обыкновенное О-большое называть "Big O"?
Все эти упрощенения и пояснения это конечно хорошо, но без главного определения выглядит несерьезно и неполно. Более того: начинать с упрощений и пояснений вредно — это может запутать
P.S. Первую статью смотрел, там определения тоже нет
Помимо перечисленных недостатков из комментариев выше, отмечу, что на практике оценка сложности/времени/памяти через Big-O нотацию даже если она применима (в частности разумные размеры констант) утыкается не в то, что циклы сложно посчитать, а в то, что вызываемые функции или действия идут не с той оценкой, которая считается (классический пример - конкатенация в цикле), или не учитывается какой-то серьёзный фактор (разница скорости доступа при превышении размера кеша или памяти, например, когда доступ становится на порядок или порядки дольше).
Слишком просто хайпануть на главном вопросе всех интервью про "Большое О", но сложнее (а) донести до новичков мысль, (б) дать полезную информацию уже чуть опытным. IMHO, больше всех в этом вопросе удалось автору книжки "Cracking the Coding Interview".
а что, если у нас есть оператор if или какие-то условные выражения. В этом случае делаем то же самое, только берем наихудший случай.
Очень наивный подход. Оно, конечно, даст правдивую оценку сверху, но эта оценка может быть слишком завышина.
Например, код:
for i in 1..n
if i == 42:
for j in 1..i
// do something.Работает за линию, а не за квадрат.
Big O нотация в Swift (часть 2 — Сокращение)