Какова будет временная сложность для вложенных циклов, содержащих экспоненциальный? - PullRequest
Новая
       7

Какова будет временная сложность для вложенных циклов, содержащих экспоненциальный?

2 голосов
/ 02 апреля 2019 
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; j += pow(i, 2))
        //some O(1) operation

Какая временная сложность для этого фрагмента? Для каждого i во внешнем цикле я вычисляю, сколько операций выполнит внутренний цикл, и нашел:

hello

Но я не знаю, как сделать математику ... А что если я поменяю часть pow на pow (i, 3) или более высокую мощность?

Любая помощь приветствуется!

edit: извините, но я решил спросить 

for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; j *= i)
        //some O(1) operation

И под высшей силой я имею в виду j * = (i * i) или j * = i * i * i ... и т. Д.

Снова извините за неправильный вопрос ...

Ответы [ 2 ]

3 голосов
/ 02 апреля 2019

Сложность O(n), как показывал @paragon. Кроме того, иногда просто подсчитывая, сколько итераций произойдет, часто выявляется сложность: 

#include <iostream>

unsigned f(unsigned n) {
    unsigned ctr = 0u;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; j += pow(i, 2)) {
            ++ctr;
        }
    }
    return ctr;
}

int main() {
    for (unsigned n = 1u; n < 9u; ++n) {
        unsigned a = std::pow(10, n) * 2;
        unsigned b = std::pow(10, n);
        std::cout << "f(" << a << ") / f(" << b << ") = " << f(a) / static_cast<double>(f(b)) << '\n';
    }
}

показывает, что он явно приближается к сложности O(n): 

f(20) / f(10) = 2.09091
f(200) / f(100) = 2.04016
f(2000) / f(1000) = 2.01001
f(20000) / f(10000) = 2.0035
f(200000) / f(100000) = 2.00105
f(2000000) / f(1000000) = 2.00032
f(20000000) / f(10000000) = 2.0001
f(200000000) / f(100000000) = 2.00003

А что если я поменяю часть pow на pow (i, 3) или более высокую мощность?

оно останется по-прежнему O(n). Это имеет смысл, поскольку чем выше показатель степени, тем больше j увеличивается, завершая свой цикл еще раньше, уменьшая сложность по сравнению с циклом i (i <= n => O(n)): 

[pow = 1]       f(20000000) / f(10000000) = 2.08026
[pow = 2]       f(20000000) / f(10000000) = 2.0001
[pow = 3]       f(20000000) / f(10000000) = 2.00001
[pow = 4]       f(20000000) / f(10000000) = 2
[pow = 5]       f(20000000) / f(10000000) = 2
[pow = 6]       f(20000000) / f(10000000) = 2
[pow = 7]       f(20000000) / f(10000000) = 2
//...

добавление к ответу @ paragon, серия

enter image description here

, где p - показатель степени. С ростом x доля сокращается, и сумма приближается к фиксированному значению (за исключением небольших значений p, я думаю)

3 голосов
/ 02 апреля 2019

Если я правильно понимаю ваш код, логарифмы не должны использоваться.Общее количество шагов должно быть 

n + n/2 + n/2^2 + n/3^2 + ...

Это геометрический ряд.Это сумма 2n.

РЕДАКТИРОВАТЬ: Как указано в комментариях, это не геометрические.Правильная сумма равна pi ^ 2/6 * n, см. https://en.wikipedia.org/wiki/Basel_problem. Но все равно есть O (n).

...