KK
А откуда такая оценка?
Количество делителей большого числа около кубического корня может быть
Size: a a a
2020 May 01
MB
Кажется верно, что это O(N**(1+eps)) для любого eps > 0
ПК
Почему сумма O(n log n)?
Потому что в n / 1 + n / 2 + n / 3 + n / 4 + ... — O(n log n)
ПК
Т.к. 1/1 + 1/2 + 1/3 + ... + 1/n — O(log n)
MB
Потому что в n / 1 + n / 2 + n / 3 + n / 4 + ... — O(n log n)
А причем тут гармонический ряд?
EZ
А причем тут гармонический ряд?
Ну это очевидная верхняя граница
MB
А, понял.
d1 <= n
d2 <= n/2
...
dk <= n/k
да, и вправду
d1 <= n
d2 <= n/2
...
dk <= n/k
да, и вправду
EZ
А, понял.
d1 <= n
d2 <= n/2
...
dk <= n/k
да, и вправду
d1 <= n
d2 <= n/2
...
dk <= n/k
да, и вправду
Ну просто все делители меньше n
EZ
Каждое число встречается 1 раз
KK
А, ну да, логично что лог тогда
ПК
Так, хм, сумма чисел от 1 до n — O(n²), но при этом она же — O(n log n)…
ПК
А, нет, неправда
ПК
Потому что n/n, n/(n - 1), n/(n - 2), ..., n/1 — не то же самое, что и 1, 2, 3, 4, ..., n
2020 May 02
ГА
Добрый день. У меня задача просто выяснить является ли орграф сильно связным или нет. Какой алгоритм можно применить?
АК
Наверное это тебе подойдет
ГА
Ок!!! СПС!!! Просто тут идет разложение на компоненты, а мне узнать сильно связные компоненты не надо, но видимо по другому никак, так как тоже такие нашёл!
IS
Ок!!! СПС!!! Просто тут идет разложение на компоненты, а мне узнать сильно связные компоненты не надо, но видимо по другому никак, так как тоже такие нашёл!
Если я правильно понимаю сильно связный это когда из любой вершины можно добраться до любой другой? ПРосто если у тебя компонент больше чем одна то сразу ответ нет. По-моему логичный алгоритм
ГА
Если я правильно понимаю сильно связный это когда из любой вершины можно добраться до любой другой? ПРосто если у тебя компонент больше чем одна то сразу ответ нет. По-моему логичный алгоритм
Ну до этого я тоже додумался))) я просто думал есть боле подходящий алгоритм просто узнать да или нет. Либо наверно взять и прервать алгоритм если уже больше одной компоненты
Ш
привет всем а в задаче найти цикл, у которого среднее арифметическое весов рёбер минимально