>> Хочешь сказать, рандомом без честных рангов вообще нельзя получить log* ?
Да!
1 2011-06-20 08:53:39
Re: Краскал (8 ответов, оставленных в Algo)
2 2011-06-20 08:50:47
Re: Краскал (8 ответов, оставленных в Algo)
Извиняюсь, я забыл про форум... мне на почту не приходит "у вас новое сообщение" :-(
Тест очень простой: растим цепочку.
1) Если мы всегда делаем p[a] = b, мы получим высоту N
2) Если мы делаем if (rand() & 1), мы получим высоту N / 2
P.S. Если делать только сжатие путей, асимптотика (аморатизированная) уже O(logN). Поэтому есть распространенное мнение, что rand() & 1 что-то дает. На самом деле, если тест случаен - он и без rand() & 1 случаен. А если тест = цепочка, то быстро работает не потому что rand() & 1, а потому что сжатие путей.
3 2011-06-10 08:03:50
Тема: Краскал (8 ответов, оставленных в Algo)
http://e-maxx.ru/algo/mst_kruskal_with_dsu
if (rand() & 1) swap (a, b);
Этот if не меняет асимптотику. Может лучше его или убрать, или переписать на честные ранги? :-) Или конкретно в случае построения MST это действительно дает оптимайз?
P.S. Если нужен тест для произвольной СНМ-задачи, на котором этот "оптимайз" ничего не дает, могу предоставить.
4 2010-11-18 00:55:40
Re: Генерирование простых чисел (4 ответов, оставленных в Problems)
Вы имеете в виду "дано k, найти k-е простое число, и так 10^5 раз"?
Одно k-е (1 <= k <= N) простое число я умею искать в лучшем случае за O(N^{2/3})
Все простые от 1 до N за O(N).