Сложность времени функции, которая содержит другую функцию - PullRequest
Новая
       16

Сложность времени функции, которая содержит другую функцию

0 голосов
/ 29 августа 2018

Может кто-нибудь дотошно объяснить, как я могу выяснить временную сложность этого кода? 

int f(int n)
{
    int sum = 0;
    while (n>1)
    {
        sum +=g(n)
        n = sqrt(n)
    }
    return sum;
}

где g (n) определяется как: 

int g(int n)
{
    int sum  = 0;
    for (int i = 1; i<n; i*=2)
        sum +=i;
    return sum;
}

Заранее спасибо!

Ответы [ 3 ]

0 голосов
/ 29 августа 2018

Несколько более конкретный способ доказать результат:

Как правильно сказано в предыдущем ответе, сложность g(n) равна O(log n). Точное число выполнений цикла в g(n) составляет floor(log2(n)) + 1.

Теперь для f(n). Значение n после m -ой итерации цикла относительно оригинального значения n составляет:

enter image description here

Исходя из этого, используя условие цикла n > 1, количество выполнений этого цикла составляет:

enter image description here

Это позволяет выразить функцию сложности f(n) в виде суммирования:

enter image description here

В (*) я использовал тот факт, что число, округленное в меньшую сторону, отличается от первоначального значения только на меньше , чем 1 (следовательно, O(1)). В (**) я использовал стандартный результат для сумм геометрических рядов.

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

Таким образом, окончательная сложность составляет всего O(log n + log log n) = O(log n), поскольку доминирует первый член.

0 голосов
/ 29 августа 2018

Большие обозначения O для описания асимптотического поведения функций. По сути, он говорит вам, как быстро функция растет или уменьшается

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

T(n) = 4 n^2 - 2 n + 2

Если мы игнорируем константы (что имеет смысл, поскольку они зависят от конкретного оборудования, на котором запускается программа) и медленнее растущих терминов, мы можем сказать, что «T (n)» увеличивается в порядке n ^ 2 »и написать: T (n) = O (n ^ 2)

Для формального определения предположим, что f (x) и g (x) - две функции, определенные на некотором подмножестве действительных чисел. Мы пишем 

f(x) = O(g(x))

(или f (x) = O (g (x)) для x -> бесконечность, чтобы быть более точным), если и только если существуют такие константы N и C, что 

|f(x)| <= C|g(x)| for all x>N

Интуитивно это означает, что f не растет быстрее, чем g

Если a - некоторое действительное число, мы пишем 

f(x) = O(g(x)) for x->a

тогда и только тогда, когда существуют константы d> 0 и C такие, что 

|f(x)| <= C|g(x)| for all x with |x-a| < d

Так что для вашего случая это будет 

O(n) as |f(x)| > C|g(x)|

Ссылка от http://web.mit.edu/16.070/www/lecture/big_o.pdf

for r from 0 to xlist:  // --> n time
       for c from 0 to ylist: // n time
         sum+= values[r][c]  
         n+1

}

Big O Нотация дает предположение, когда значение очень большой внешний цикл будет выполняться n раз, а внутренний цикл - n раз

Предположим, что n -> 100, чем всего n ^ 2 10000 времен выполнения

0 голосов
/ 29 августа 2018

g является логарифмическим по своим аргументам (если вы передадите его n, его цикл будет повторяться log[2](n) раз, поскольку требуется столько итераций для удвоения i, чтобы достичь n.

f вдвое логарифмичен - он вдвое уменьшает показатель от n в каждой операции для log[2](log[2](n)) повторений.

Мы можем игнорировать тот факт, что g - это отдельная функция - фактически это цикл, вложенный в другой цикл. Мы можем найти лучший предел, если точно проанализируем, как количество повторений g уменьшается по мере продвижения f, но O(log n * log log n) достаточно хорошо. (Теория сложности похожа на морепродукты: хотя «я ел тунца» может быть правильный ответ , «я ел рыбу» не так.)

EDIT:

Однако правильный ответ - O (log (n)) (окончательный тестовый ответ), и я не понимаю, почему ....

Как я уже сказал:

Мы можем найти лучший предел, если проанализируем, как именно количество повторений g уменьшается по мере того, как f прогрессирует

но, честно говоря, это легче сделать из результатов, чем из кода. Скажем, n начинается с 65536. Это даст нам 16 итераций g. Корень этого 256, что позволит g запускаться 8 раз. Далее 16, за 4 итерации g. Затем 4 для 2 и 2 для 1. Это выглядит как геометрическая прогрессия: 16+8+4+2+1 = 32-1, где 32 равно 2 * log[2](65536), что согласуется с O (log n).

Или вы могли заметить, что на первой итерации f будет много итераций g, по сравнению с которыми все другие вызовы g не имеют значения (исчезают логарифмически). Поскольку этот первый вызов g - это O (log (n)) `, мы можем просто обрезать его и сказать, что это сложность.

...