Лайфхак, чтобы понять эту херню - посмотри на графики, что "агрессивнее" растет, то и хуже
Тоесть там где линия резко возрастает, то это хуже?
Да. Их рисуют по принципу сложность вместо оси Y, количество элементов на вход (то самое n) вместо Х
Значит n2 хуже чем nlogn?
Могу вот это статью посоветовать, самый огонь, чтобы на пальцах и понятно про сложность: https://dou.ua/lenta/articles/what-you-should-know-about-algorithms/
угу, тут же зависимость времени от N, всё видно
Кстати почему такие вопросы на собесах задают, а в коде никогда таких не видел...
А где основание логорифма?
У меня такое ощущение, что не увидишь, пока не убьешь по незнанке производительность
Это да, есть такое
*Логарифм.
Да, очепятка, извиняюсь
Не торопись пока с Логарифмом) В Универе расскажут). Я то профукал все
Так мы уже интегралы проходим, логарифмы фигня же
в ассимптотике constant factors опускают, поэтому O(2N) => O(N) и с логарифмом также, всё равно какое основание
Ну это не совсем правильно тогда. Коэффициент и основание логарифма разные вещи же, при повышении основания логарифма значение уменьшается.
Так это если бы было 2N и 2logN, то тогда можно было бы двойки сократить. Иначе N != logN, равно только при основании 1
https://stackoverflow.com/questions/1569702/is-big-ologn-log-base-e
Если смотреть на реальные задачи алгоритмов вроде бинарного поиска - то фактически там основание 2 чаще. У стохоастических - чаще e. Ну и множитель реально неинтересен. О(2N)=О(N) если взять два процессора
То есть нам нужно просто проанализировать как растёт логарифм по сравнению с O(N)?
Да.
В 16 лет?
У нас лицей Ришельевский в Одессе, 14 математик в неделю норма
А в сколько?
А так я физик вообще
Друг там учится, а потом эти математики поступают в рыбку)))
О, ты с Одессы?
Киев
Рыбка это на моряка? Я особо не шарю в престижах вузов или училищ
Типа))
Зашквар если честно
Ну у нас тоже есть те, кто не учатся. Понятно, что средние знания выше может, чем у обычных шк, но есть те, кто не учатся вообще, не от учебного заведения зависит твоя судьба )
Обсуждают сегодня