AA
За один проход
Size: a a a
2021 February 11
SP
За один проход
если он случайно оказался отсортирован то прокатит и за один )
AA
Зачем сортировать? Идешь и запоминаешь топ so far. Перезаписываешь если встретил более лучший топ
S
Почему, если отсортирован, то за логарифм
S
Если рандомный, то просто 1 проход же
SP
Зачем сортировать? Идешь и запоминаешь топ so far. Перезаписываешь если встретил более лучший топ
ты сейчас описал сортировку пузырьком
AA
ты сейчас описал сортировку пузырьком
Пузырек квадратичное время даёт. А тут линейное
SP
Пузырек квадратичное время даёт. А тут линейное
ты придумал сортировку за линейное время?
AK
Зачем сортировать? Идешь и запоминаешь топ so far. Перезаписываешь если встретил более лучший топ
Это O(N log K)
AA
Тогда дефайн «топ»
SP
Это O(N log K)
вроде ничего лучше логарифма не придумали
SP
Тогда дефайн «топ»
так может быть топ 1 топ 2 топ 3 )) или возьми предпоследний с конца и сложи с предпоследним с начала
SK
вроде ничего лучше логарифма не придумали
radix
AA
А блин я про максимальный подумал
AK
вроде ничего лучше логарифма не придумали
В худшем случае - нет. Но для реального мира есть и более эффективный алгоритм, чем проход хипом
AA
Ну да, там логарифмическок время
AK
radix
А если не исчислимое?
SP
В худшем случае - нет. Но для реального мира есть и более эффективный алгоритм, чем проход хипом
в худшем вроде есть алгоритмы что факториал дают.
S
вот надо тебе взять топ результат из списка
Ну такое условие звучит как задача найти один конкретный элемент
SP
я про сферический набор данных в вакууме. лучше лог-н вродь нет ниче. комплексити н - это только возможно для частных случаев и конкретных наборов данных но никак не средуха.