Wataru

Предполагаю, что это известная задача, где надо минимизировать количество бросков в хужшем сулчае. Задача решается динамическим программированием.

Пусть C(n,k) - сколько надо в худшем случае бросков, если мы знаем, что предмет разбивается при бросании с 1..n и можно сделать k неудачных бросков.

С(n,k) = min_i=1..n-1 ( max(C(i,k-1), C(n-i, k)) )) + 1

База - C(1, k) = 0; C(n, 1) = n-1.

Судя по названию функции (sum) вам надо найти сумму чисел. Это делается в одно действие без циклов вообще.

Если бы были нужны только числа делящееся на 3, то их сумма - f(n, 3)=3*floor(n/3)(floor(n/3)+1)/2. Эта формула получается вынесением 3 за скобки в сумме и дальше применением формулы армфметической прогрессии.

Чтобы взять сумму делящихся на 3 или 5 надо взять сумму делящихся на 3, прибавить сумму делящихся на 5 и вычесть сумму делящихся на 15. Потому что делящиеся на 15 были подсчитанны 2 раза в первых слагаемых. Т.е. ответ - f(n,3)+f(n,5)-f(n,15)

Можно в несколько раз с оптимизировать, переписав на C++ c векторизацией (SSE там всякие). Тогда сравнение двух строк будет 1-2 инструкции вместо 15. Еще можно распаралеллить вычисления. Но все эти оптимизации все равное не позволят вам быстро считать для 100000 строк. Что уж говорить, сама матрица будет занимать минимум 10 гигабайт, если аккуратно на C писать или типизированный numpy массивы использовать. А так она и все 20 и 40 гигабайт займет запросто.

И ничего сильно более быстрого тут не получится, если вам нужна вся матрица - придется пару минут ее считать в лучшем случае. Вот если вы ее используете для каких-то еще вычислений (например, вы для каждой строки считаете, сколько близких к ней есть в списке), то можно принципиально ускорить решение не вычисляя матрицу, а считая искомое количество сразу.

Тут не нужно решето. Надо просто отдельно проверить каждое число на простоту.

Подсказка: Если число не простое, то у него есть простой делитель не больше корня (потому что иначе - есть хотя бы 2 делителя и они оба больше корня и их произведение уже больше самого числа).

Вам надо арктангенс брать от отношения, а не тангенс (y2-y1) / (x2-x1).

Это называется интерполяция. Вы знаете, что f(a) = 10, f(b)=5. Вам надо найти f(c), при чем f должна попадать под здравый смысл (монтонная, непрерывная функция).

например, можно взять линейную инерполяцию, тогда f(x) = 10-(x-a)/(b-a)*5.

Работает медленно, потому что вы обрезаете входной массив каждый раз. Для этого приходится обходить и копировать всю нужную часть. Поэтому суммарное время работы будет O(n).

Чтобы работало быстро вам надо не менять lst, а помнить индексы границ текущего куска.

Ещё, вам надо останавливаться, когда рассматриваемый кусок станет пустым, чтобы решение не вылетало, если искомого числа в списке нет.

И последнее, в питоне есть операция целочисленного деления - //. Используйте ее вместо приведения к int после деления.

Заведите массив из нулей. Для каждого отрезка сделайте +1 в координату его левого конца и -1 в координату, следующую за правым концом.

Потом пройдитесь по массиву слева-направо, поддерживая счетчик. Прибавляйте к счетчику значение массива и выводите значение счетчика.

Это если вам надо весь массив, как в примере, выводить. Не знаю специфику вашей задачи, может эффективнее будет класть в массив пары {координата, +-1} и сортировать. Потом точно также обойти слева направо поддерживая счетчик.

Генерируются они так:

Есть у вас список уже сгенеренных чисел, изначально содержит только 1.

Вы добавляете в список сделющее число, пока не наберете необходимое количество.

Поддерживайте 3 указателя (изначально на первое число), которые указывают на первые неиспользованные числа для домножения на 2, 3 и 5.

Каждый раз берете и сморите что лучше - взять число из первого указателя, домножить на 2, взять число из второго домноженное на 3 или из последнего указателя и домножить на 5. Кладете это число в список и сдвигаете указатель.

Пример:
шаг 1.
указатели: 1, 1, 1
список: {1}
варианты:1*2, 1*3, 1*5. Лучший - 2.

шаг 2.
указатели: 2, 1, 1
список: {1, 2}
варианты:2*2, 1*3, 1*5. Лучший - 3.

шаг 3.
указатели: 2, 2, 1
список: {1, 2, 3}
варианты:2*2, 2*3, 1*5. Лучший - 4.

шаг 4.
указатели: 3, 2, 1
список: {1, 2, 3, 4}
варианты: 3*2, 2*3, 1*5. Лучший - 5.

Есть неалгоритмический способ ускорить ваше решение - храните в каждой ячейке массива не одну цифру - а несколько. Фактически, проводите вычисления в системе счисления 10000, вместо 10. Или даже 1000000000 - но тогда надо временные вычисления (умножение) делать в int64_t, чтобы переполнения не было.

Еше, при выводе такого числа надо выводить ведущие нули для всех ячеек, кроме самой старшей.

Есть и алгоритмический способ - но он сложнее. Есть алгоритм бинарного возведения в степень. Суть в том, что вы возводите число в квадрат и домножаете на базу если надо.

Но в таком виде алгоритм будет даже медленнее на больших числах. Ему потребуется O(log K) умножений большого на большое (которое делается за O(L^2), где L - длина числа, которая будет O(K)). Итоговая сложность этого алгорима будет O(K^2 log K).

Когда как ваше текущее решение делает K коротких умножений (Каждое - O(K)) - всего O(k^2) операций. Но если применять быстрое умножение длинных чисел через быстрое преобразование Фурье то итоговая сложность будет O(K log^2 K log log K). Для power=100 особо вы разницы не почуствуете, даже медленнее будет, но вот при каких-нибудь 10000 уже будет заметно быстрее.

Советую попробовать обычные оптимизации, прежде чем браться за преобразование фурье.

Еще, вместо хранения конца числа в виде особого значения 10 - вам стоит отдельно хранить длину числа в какой-то переменной с говорящим названием (хотя бы len). Тогда код будет сильно читабельнее.

Это задача о многомерном рюкзаке (multi-dimensional knapsack). Каких-то простых трюков, как с обычным одномерным рюкзаком тут нет. Только перебор с отсечениями.

Еще можно свести задачу к целочисленному линейному программированию. Вводите переменные - сколько штук каждого пункта съели, составляете линейные уравнения. Потом можно это все скормить какому-нибудь решателю. Сейчас много библиотек и они довольно быстро такие задачи щелкают. Гуглите "integer linear programming solver".

Вы наткнулись на важное свойство ассимптотического анализа. O(n^2) -означает, что на достаточно больших n, время работы будет примерно n^2 с точностью до константы. Эта самая константа может быть хоть 0.5, хоть 10000000.

Сравните 2 алгоритма:

// n(n-1)/2 инкремента.
for(i = 0; i < n; ++i){
  for (j = i+1; j < n; j++) {
    cnt1++;
  }
}
// n^2 инкремента.
for(i = 0; i < n; ++i){
  for (j =0; j < n; j++) {
    cnt2++;
  }
}

Оба алгоритма имеют O(n^2) сложность, но один делает примерно в 2 раза меньше операций.

Суть в том, что хоть алгоритмы и работают с одинаковой ассимптотикой, они могут работать разное время! Особые странности могут быть при маленьких n. O(n log n) алгоритм часто может быть медленнее O(n^2) алгоритма. Поэтому все настоящие реализации сортировок для маленьких массивов запускают более тупые квадратичные алгоритмы.

Если же вы хотите показать только ассимптотику, то возьмите n побольше, и тогда эти 30% будут незаметны по сравнению с десятикратным замедлением O(n^2) относительно O(n log n). Или нормируйте ваши сортировки. Искуственно ускорьте одни алгоритмы и замедлите другие, чтобы получить именно тот результат, который вы хотите. Но это как-то нечестно что ли. Если же вы все-таки хотите именно этого, назначьте каждой сортировке время C\*n^2 или С\*n\*log n миллисекунд. Прогоните алгоритмы сортировки без визуализации, подсчитайте, сколько операций замедления вы бы сделали (тот же самый код, что у вас, только вместо usleep() делайте sleep_count++). В конце подсчитайте коэффициент замедления - сколько каждый usleep должен спать, чтобы суммарно sleep_count их спал заданное время. И запускайте каждую сортировку уже с подсчитанными параметрами для usleep.