Я реализовал алгоритм для решения NP-жесткой задачи оптимизации. Сложность этого алгоритма O(sum (k = 1 to n) of k^n). Я знаю, что O(n^(n+1)) является верхней границей, но я не знаю, является ли она плотной. Какова жесткая верхняя граница этого алгоритма: O(n^n), O(n^(n+1)) или что-то еще?Какова жесткая верхняя граница этого алгоритма?
Благодаря
Ответ O(sumk=1n kn) = O(nn). Чтобы убедиться в этом, обратите внимание, что сумма может, с ошибками с суммарным размером O(nn), быть заменена параллельным интегралом. (Сумма представляет собой интеграл ступенчатой функции. Оттенки различия между ступенчатой функцией и непрерывностью, а затем сдвигайте их. Так как функция монотонно возрастает, сумма этих ошибок вписывается в самый последний член.) Решите определенную и вы завершаете оценку xn+1/(n+1) по адресу n и 1. Это выходит на O(nn), чтобы перейти с предыдущим сроком ошибки такого же размера.