Comments 31
Так а в чем исходная задача-то? Из вашего потока сознания вообще непонятно.
Я отреверсинжинирил из его потока сознания так: дана матрица KxM заполненная числами по правилам таблицы умножения. Нужно найти N е число в матрице в порядке возрастания
Я вообще ничего не понял. Где задача? Какая задача? Кроме непонятного набора потока слов я тут вообще ничего не увидел.
Вопрос "не как?", вопрос "зачем?".
Очевидно, что, если не учитывать повторений чисел в списке, то позиция k-го числа в бесконечной таблице умножения равна k. Пока не будем рассматривать ограничения, вызванные тем, что m < k и n < k, а обратим внимание, что количество повторений каждого числа в таблице равно количеству его двучленных факторизаций, то есть разбиений на множители (не обязательно простые). В огромной (m >= k и n >= k) таблице умножения для решения нашей задачи надо искать сумму ряда S(z) = F(1)+F(2)+...F(z), где F(x) – количество двучленных факторизаций натурального числа x, а z – минимальное натуральное число, для которого S(z) >= k. Двучленные факторизации, в свою очередь, являются подмножеством всех возможных факторизаций.
Известно, что для поиска факторизаций перебор делителей не является наиболее эффективным алгоритмом. Поэтому, если поставлена задача найти наиболее эффективный алгоритм (а точные требования к решению непонятны даже из постановки на литкоде, не то, что из статьи на хабре), то надо копать в сторону именно продвинутой факторизации, а это достаточно серьёзная математика – алгоритм Полларда, вот это всё. Тут вообще не нужен поиск в массиве, а нужен грамотный перебор факторизаций (с учётом добавочных граничных условий по m и n и с учётом двучленности). Лишние значения, среди которых надо было бы искать, при переборе просто не будут образовываться.
Сложность перебора делителей составляет O(sqrt(N)*log(N)^2), в то время как сложность алгоритма Полларда составляет O(N^(1/4)). Различие для больших N грандиозно, поэтому предложенный автором алгоритм в любом случае очень неэффективен.
Решение легко проверить в смысле найденной величины, но нифига не легко проверить в смысле эффективности. Навскидку, построение наиболее эффективного алгоритма – это не решённая математическая проблема. А даже приблизительно эффективный алгоритм вспотеешь программировать. По сложности и бессмысленности задачи, думаю, это уровень международной олимпиады по программированию. На литкоде не зря стоит уровень Hard.
Поверхностный взгляд на решения на литкоде показывает, что там вроде бы как никто даже и не пытался думать в эту сторону, и предлагаются простые неэффективные решения с бинарным поиском среди перебора делителей.
Фактически, наивный поиск k методом перебора делителей имеет факториальную сложность. Действительно, если число z раскладывается на p простых делителей, то в таблице умножения оно встретится в количестве (p-1)!/2 раз. Для решения задачи нам совершенно не нужно вычислять и просматривать все эти (p-1)!/2разбиений. Достаточно того, что мы знаем их количество.
правильно ли я понимаю, что эта задача, но с бесконечной таблицей, решается за O(1): надо из k вычесть максимальную сумму арифметической прогрессии, чтобы узнать диагональ. Неужели с конечной такие сложности нужны?
Знание диагонали нам не поможет.
k=(1+n)n/2
допустим k=16, тогда n=5.18
округляем n к меньшему, (1+n)n/2=15 Получаем, что наше число первое (16-15) на 6й диагонали, т.е. 6
Я не понял, как Вы считаете, но для k=16 ответ 7:
1 2 2 3 3 4 4 4 5 5 6 6 6 6 7 7
Из общих соображений, тут так просто не разрулить, потому что повторитель числа зависит от его простоты. Число повторяется 2 раза тогда и только тогда, когда оно простое, а это вычислительно сложно проверяется.
у вас таблица сдвинута, по ссылке на литкод 12233...
Да, поправил, но это в данном случае неважно, следующая тоже 7.
В связи с этим и 1 - единственное простое, которое повторяется 1 раз.
чтобы узнать позицию по диагонал: если разница между k и суммой прогрессии четное, то верхняя часть, если не четная то нижняя. Так мы узнаем x и y, перемножив получим ответ.
Большие различия, которые вы не подобьёте округлением, начинают появляться с числа 30, являющемся минимальным произведением 4 простых. А для него надо рисовать таблицу умножения до 30x30.
Если из каждого ряда взять 1/n первых элементов (n номер ряда), то они будут меньше всех остальных в таблице. Если взять за сумму ряда порядковый номер нужного элемента K, то можно посчитать множитель из первого ряда, взяв который сумма ряда будет K (он может оказаться и больше, чем в таблице). Но в целых числах это всё считается не прям сразу и погрешность большая на малых числах.
Но как отправная точка может сгодится кому. Как асимптоматика в принципе вообще очень хорошо должно быть
да, похоже вы правы.
Очень обрывочно и нестрого описано решение. Ничего непонятно. Советую подредактировать статью, добавив туда ту же ссылку на литкод, например.
Есть решение этой задачи за O(min(m,n)*log (mn)): Стандартный прием — дихотомия по товету. Бинарным поиском переберем ответ (число x ниже). Внутри будем считать, а какую же позицию число x имеет в сортированном списке. Если позиция меньше искомой k, то число увеличиваем, иначе уменьшаем. Можно быстро найти позицию числа x в сортированном массиве, просто посчитав, а сколько существует чисел меньших его. Для этого можно просуммировать количество меньших чисел в каждой строке: это будет floor((x-1)/i), где i — номер строки.
Тут правда надо аккуратно с повторяющимеся числами. Для этого надо найти такое минимальное x, что количество чисел меньших x в массиве, строго меньше k.
Вы в оценке сложности не учли сложность построения самого массива с таблицей умножения, то есть, собственно, сложность умножения чисел. А это весьма трудоёмкая (O(mn)), но не обязательная операция для нахождения ответа.
Вас же не просят напечатать искомую таблицу, а просят просто вычислить значение k, совпадающее с индексом в ней. Примерный подход к решению этой задачи я описал выше.
Вы в оценке сложности не учли сложность построения самого массива с таблицей умножения
Возможно вы невнимательно прочитали мой комментарий. Не надо никакую таблицу строить. Можно за O(1) в каждой строке подсчитать меньшие числа в каждой строке: в строке i, где числа вида i*x можно подсчитать числа меньшие k за константу (просто поделив k-1 на i и округлив вниз).
Вот пример: строка для 10 {10, 20, 30, 40, 50, 60...} Чисел меньше 24 тут 23/10 = 2. меньших 50 — 49/10=4, меньших 3 — 2/10 = 0. Все совпадает.
Описанный же вами метод требует раскладывать на множители каждое число от 1 до N. Поэтому сложность его будет O(n*f(n)), где f(n) — сложность какого-то офигенно быстрого алгоритма разложения на множители. Если f(n) > log n, то ваше решение уже хуже. И насколько я знаю, методов подсчета делителей за O(log n) пока никто не придумал, так что ваше решение, какие бы продвинутые методы оно не использовало, будет медленнее приведенного мной.
Мой метод требует раскладывать на множители каждое число не до N, а до гораздо меньшего (факториально меньшего) числа.
На очень больших m и n таблица умножения будет содержать много чисел с большим количеством делителей, которые будут формировать последовательности повторяющихся чисел с повторителем, факториально зависящим от количества простых делителей, а сам повторитель при этом можно вычислить за одну операцию, уже разложив на делители. А вам придётся перебирать все n строк.
Например, число 110435831458355913510 имеет 16 простых делителей, что мы установим эффективным алгоритмом факторизации примерно за 100 тысяч операций. Узнав это, за одно действие мы получаем, что оно встретится в таблице умножения 653837184000 раз, то есть 653 миллиарда раз (если я правильно посчитал число сочетаний). Для того, чтобы это определить вашим пересчётом (хоть я и не понял до конца, как он работает), вам надо оценить sqrt (110435831458355913510) = 10 миллиардов строк. Таким образом, я получил приращение k на 653 миллиарда, затратив 100 тысяч операций, а вы – затратив 10 миллиардов операций. Конечно, здесь есть некоторый элемент жульничества с моей стороны, потому что далеко не все числа раскладываются на такое большое количество делителей. Но интуитивно ясно, что чем дальше, тем количество делителей будет в среднем больше.
Мой метод требует раскладывать на множители каждое число не до N, а до гораздо меньшего (факториально меньшего) числа.
В задаче дано 1 <= k <= m * n. Т.е. получиться может любое из всех возможных чисел в таблице до mn. Насколько я понял, вы увеличиваете число на 1, потом вычитаете из k количество повторений числа в таблице. Т.е. что бы получить в ответе число nm, вам придется этот счетчик до mn догнать. Т.е. ваше решение o(nm) в любом случае!
Но интуитивно ясно, что чем дальше, тем количество делителей будет в среднем больше.
А еще тем больше будет чисел, не встречающихся в таблице, имеющих ровно 0 разбиения на 2 множителя до n и до m. Поэтому если где-то вы смогли миллиарды чисел проскочить за счет числа с большим количеством множителей, вам все эти же миллиарды потом придется прибавлять нули. Только еще затратив кучу вычислений для нахождения этого нуля.
В задаче дано
1 <= k <= m * n. Т.е. получиться может любое из всех возможных чисел в таблице до mn. Насколько я понял, вы увеличиваете число на 1, потом вычитаете из k количество повторений числа в таблице. Т.е. что бы получить в ответе число nm, вам придется этот счетчик до mn догнать.
Если k = m*n, тогда, конечно, придётся догонять счётчик до mn (что означает факторизацию чисел вплоть до sqrt(mn)). Но это крайний случай.
А еще тем больше будет чисел, не встречающихся в таблице, имеющих ровно 0 разбиения на 2 множителя до n и до m. Поэтому если где-то вы смогли миллиарды чисел проскочить за счет числа с большим количеством множителей, вам все эти же миллиарды потом придется прибавлять нули. Только еще затратив кучу вычислений для нахождения этого нуля.
Мы с вами, похоже, руководствуемся разными граничными оценками. Я в своих рассуждениях исходил из того, что m и n очень велики, а k достаточно мало по сравнению с ними, так что задача по существу похожа на поиск в бесконечной таблице умножения, а фактически мы ищем в основном в левом верхнем углу таблицы m*n. Вы же описываете поиск, эффективный в правом нижнем углу таблицы.
Получается, что эффективный алгоритм должен оценить сравнительную величину k и m*n, и в зависимости от этого двигаться по разным веткам.
В целом же простые числа встречаются всё реже и реже по мере своего увеличения, поэтому при возрастании m и n доля нулей и прочих малых чисел будет всё меньше и меньше.
Я в своих рассуждениях исходил из того, что m и n очень велики, а k достаточно мало по сравнению с ними, так что задача по существу похожа на поиск в бесконечной таблице умножения, а фактически мы ищем в основном в левом верхнем углу таблицы m*n. Вы же описываете поиск, эффективный в правом нижнем углу таблицы.
Скорее я оцениваю худший случай. O() для них и считается. Но согласен, для мелких k ваш алгоритм будет быстрее.
Одна задачка на литкоде