Аз маҳдудиятҳо ба идея
Муаллифон маҳдудиятҳоро чунон интихоб мекунанд, ки ҳалли дар назар дошташуда ҷой шавад ва ҳалли аёни сусттар ҷой нашавад. Ҳангоми маҳдудияти вақти тақрибан як сония, калонтарин n нишонаи қавӣ аст:
- n ≤ 10. Ҳамаи тартибҳоро санҷед: 10! ≈ 3,6 · 10⁶.
next_permutation-ро истифода баред. - n ≤ 20. Ҳамаи зермаҷмуъҳоро санҷед: 2²⁰ ≈ 10⁶. Ҳар ҷавобро бо рекурсия созед.
- n ≤ 500. Ҳамаи сегонаҳо, n³ = 1,25 · 10⁸: се сикли дохилӣ.
- n ≤ 5 000. Ҳамаи ҷуфтҳо, n² = 2,5 · 10⁷: ду сикли дохилӣ.
- n то 2 · 10⁵ ё 10⁶. n log n: танзим, ҷустуҷӯи дуӣ барои ҳар ҷузъ,
setваmap. - n то 10⁷ ё 10⁸. Як гузариш бо қадамҳои оддӣ ва вуруду баромади зуд.
- n то 10¹². √n қадам: тақсимкунандаҳо то √n.
- n то 10¹⁸. log n ё формула: ба ду тақсим кардан, рақамҳо, арифметика.
Инро дар ду самт бихонед. Ҳангоми n ≤ 5000 сикл барои ҳамаи ҷуфтҳо интизор меравад. Ҳангоми n ≤ 2 · 10⁵ ҳамин сикл 2 · 10¹⁰ қадам мекунад: идеяи аёнӣ ҷавоб нест.
Вақте дар вуруд ду андоза ҳаст, n адад ва q савол, онҳоро зарб кунед: n · q нархи усули «ба ҳар савол бо як гузариш ҷавоб додан» аст. Вақте t тест ҳаст, санҷед, ки оё шарт ҷамъи n-ро аз рӯи ҳамаи тестҳо маҳдуд мекунад. Одатан маҳдуд мекунад, ва ҳамин ҷамъ n-и лозимӣ аст.
Рӯйхат роҳнамост, на қонун: қадамҳои оддӣ аз 10⁸ дар як сония тезтар иҷро мешаванд, вале қадамҳои вазнин, масалан амалҳои map, суст.
Ҳисоби дақиқи сиклҳои дохилӣ
Инҳо ҳисобҳои дақиқанд ва як сикли дохилӣ, ки аз намуди зоҳириаш хеле кӯтоҳтар аст:
iаз 0 то n − 1,jаз i + 1 то n − 1: n(n − 1) / 2 гузариш, ҳар ҷуфт як маротиба. Барои n = 5000 ин 12 497 500 аст.i<j<k: n(n − 1)(n − 2) / 6, ҳар сегона як маротиба. Барои n = 500 ин 20 708 500 аст.iаз болои n ҷузъ,cаз болои 26 ҳарф: 26 · n.dаз 1 то n, ваm= d, 2d, 3d, … то n: n/1 + n/2 + n/3 + …, тақрибан n · ln n. Барои n = 10⁶ ин 13 970 034 аст.
Охирин ба n² монанд аст, вале сикли дохилӣ қадамҳои торафт калонтар мегузорад. Ана ин ҷо он фоида медиҳад:
Барои ҳар адад аз 1 то n чоп кунед, ки он чандто тақсимкунанда дорад. 1 ≤ n ≤ 10⁶.
Вуруд
Баромад
Санҷидани тақсимкунандаҳои ҳар адад то решаи квадратии он тақрибан √x қадам барои ҳар x меарзад. Саволро чаппа кунед: бигзор ҳар аз болои ададҳое гузарад, ки онҳоро тақсим мекунад, яъне d, 2d, 3d ва ғайра.