вычислить временную сложность заданной функции на C

#c #time

#c #время

Вопрос:

Мне нужно вычислить временную сложность функции f3:

Моя проблема в том, что мне не удается вычислить, сколько раз я могу применить функцию sqrt () к n, пока она не станет меньше 1: n^0.5^k < 1 я могу предположить, что временная сложность sqrt () равна 1. есть идеи, как я могу получить значение k из n^0.5^k < 1 ? если мне это удастся, то, я думаю, оценить сумму ряда: n/2, (n^0.5)/2, (n^0.5^2)/2,... было бы проще.

1. Пожалуйста, не включайте coode в качестве изображения.

2. Просто предположим, что существует компилятор, который преобразует код в эквивалент » int f3(int n) { return pre_computed_table[n]; } «‘ и указывает, что (для гипотетического компилятора) код равен «O (1)». Помимо этого; Я даже не уверен, что вы можете гарантировать, что код когда-либо будет завершен — для конкретных входных данных это может быть «O (бесконечность)» (просто думая о переполнениях, которые возникают в случае, подобном » f3(INT_MAX) «, у меня болит мозг).

3. На самом деле, мой мозг не так сильно болит. Относительно легко увидеть, что, например g3(INT_MAX) , он никогда не выйдет for(i = 1; i < n; i *= 2) из цикла «» (технически это неопределенное поведение, но я все равно ожидаю, что «цикл навсегда»).

4. @Brendam Почему вы предполагаете, что компилятор создаст предварительно вычисленную таблицу? Это был бы действительно тупой компилятор

Ответ №1:

Я покажу нижнюю и верхнюю границы.

Сначала мы вычисляем стоимость g3 .

Возьмем, к примеру, n = 2^16 .

Сколько итераций мы делаем в цикле for?

 i=2^0, i=2^1, i=2^2, i=2^3... < 2^16

Более или менее, это будет 16 шагов. Итак, стоимость g3 равна O(log(n)) .

Теперь давайте попробуем вычислить f3 . Поскольку он используется g3 внутри цикла, он будет выглядеть следующим образом:

 log(n)   log(n^(1/2))   log(n^(1/4))   log(n^(1/8))   ...

Это наверняка больше, чем log(n) , поэтому мы могли бы принять log(n) за нижнюю границу.

Теперь, чтобы вычислить верхнюю границу, мы должны подумать, сколько итераций выполняет цикл?

Возьмем еще раз 2^16 в качестве примера:

 2^16, 2^16^(1/2), 2^16^(1/4), 2^16^(1/8), 2^16^(1/16),

Это оказывается:

 2^16, 2^8, 2^4, 2^2, 2^1

И на следующей итерации мы остановимся, потому sqrt(2) что округляем до 1.

Итак, в общем случае, если n=2^2^k мы делаем k итераций. Это log(log(n)) . Это означает, что мы могли бы сказать log(n)*log(log(n)) как верхнюю границу.

Вероятно, есть более скорректированное решение, но оно должно быть довольно точным.

1. спасибо за подробное решение, я ошибся во временной сложности g3, я знаю, что решение есть log(n) , но как я могу иметь ту же верхнюю границу?

2. @David Возьмем, к примеру, 2^8 = 256 , сколько итераций выполняет цикл g3 ? Также примите во внимание, что я использую логарифм по основанию 2, так log(2^n) = n что .

3. я думаю, что нашел что-то, используя правила регистрации: log(n) log(n^(1/2)) log(n^(1/4)) log(n^(1/8)) ... ` = log(n n ^(1/2) * n ^ (1/4) * n ^(1/8) …) = log(n^(1 1/2 1/4 1/8 …));

4. теперь, n^(1 1/2 1/4 1/8 ... k) < n^2 сделав это: log(n^(1 1/2 1/4 1/8 ... k) < log(n^2) и верхняя граница равна O(log(n))

5. Это потрясающе, вы нашли решение лучше моего 🙂