Big O нотация в Swift (часть 2 — Сокращение)

[vadimr]

Очень вводящий в заблуждение цветной график на рисунке. Зачастую на практике сравнительная эффективность алгоритмов определяется константной частью, при этом кривые не исходят из одной точки (0, 0), как показано на графике.

[Dinozavr2005]

спасибо, учту замечания

[Superdry]

Хорошо было бы привести примеры для ловушек.

[Dinozavr2005]

https://github.com/dinozavr2005/ios-library/tree/main/Алгоритмы/Arcade

накидал примеров, можно попробывать посмотреть и постараться разобраться что там происходит

[izvolov]

Программисты на Свифте профильной литературы не читают и в школе институте не учатся?
Зачем обыкновенное О-большое называть "Big O"?

[Dinozavr2005]

я учился на экономе, правильно получается О-большое? буду иметь ввиду сенкс

[izvolov]

https://ru.wikipedia.org/wiki/«O»большое_и«o»_малое

[Dinozavr2005]

спасибо, почитаю

[MentalBlood]

Все эти упрощенения и пояснения это конечно хорошо, но без главного определения выглядит несерьезно и неполно. Более того: начинать с упрощений и пояснений вредно — это может запутать

P.S. Первую статью смотрел, там определения тоже нет

[Dinozavr2005]

Получается чтобы статья топ была надо смешивать определения и разьяснения?

[MentalBlood]

Это такое смешение когда в начале дается строгое полное определение, а за ним следуют разъяснения для тех кто сходу не понял

[Dinozavr2005]

понял, спасибо)

[speshuric]

Помимо перечисленных недостатков из комментариев выше, отмечу, что на практике оценка сложности/времени/памяти через Big-O нотацию даже если она применима (в частности разумные размеры констант) утыкается не в то, что циклы сложно посчитать, а в то, что вызываемые функции или действия идут не с той оценкой, которая считается (классический пример - конкатенация в цикле), или не учитывается какой-то серьёзный фактор (разница скорости доступа при превышении размера кеша или памяти, например, когда доступ становится на порядок или порядки дольше).

[Tuxman]

Слишком просто хайпануть на главном вопросе всех интервью про "Большое О", но сложнее (а) донести до новичков мысль, (б) дать полезную информацию уже чуть опытным. IMHO, больше всех в этом вопросе удалось автору книжки "Cracking the Coding Interview".

[wataru]

а что, если у нас есть оператор if или какие-то условные выражения. В этом случае делаем то же самое, только берем наихудший случай.

Очень наивный подход. Оно, конечно, даст правдивую оценку сверху, но эта оценка может быть слишком завышина.

Например, код:

for i in 1..n
  if i == 42:
   for j in 1..i
    // do something.

Работает за линию, а не за квадрат.