Тема: Deliteli
Mojno li za O(Koli4est4o deliteli 4isla n) naiti vse deliteli 4isla n? ili Za skolko mojno naiti?))))))))
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Deliteli
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Mojno li za O(Koli4est4o deliteli 4isla n) naiti vse deliteli 4isla n? ili Za skolko mojno naiti?))))))))
Да, конечно можно. Факторизуем N:
N = a1^p1 ... ak^pk
тогда любой делитель имеет вид:
a1^i1 ... ak^ik,
где 0<=ij<=p1
Ну и собственно, все такие наборы чисел (i1...ik) можно перебрать рекурсивно, и за O от их количества.
Можно ровно за O(sqrt(N)).
Просто перебираем все делители до корня, допустим это I,тогда N / I это тоже нейкий делитель,что бы не было повторов делителей просто припишем условие (I < N / I) тогда N / I тоже делитель.
Ну да. Но бывают задачи, когда нужно именно за O(кол-ва делителей), т.е. ограничения специально подобраны.
Ну тогда нужно еще найти факторизацию. А без разных быстрых методов она как раз работает за O(sqrtN).
Я вот это хотел пометить. Факторизация занимает такое же время,а что бы писать быстрые алгоритмы нужно кучу времени.
Факторизовать можно быстрее. Найти все простые числа до корня, тем же решетом Эратосфена, и перебирать не все числа до корня, а только их.
Хотя построение решета займет тоже самое время, но это будет предпроцесс, так что если надо находить для множества чисел, то это будет выгодно.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Deliteli