Блог

Я запутался в том, как создать функцию T (n) для измерения времени вычисления для вложенного бесконечного цикла. Вот код:

 x=1;
for(int i = 0;i<n-1;i  ){
     for(int j = 1; j<=x; j  ){
        cout << j << endl;
        x*=2;
     }
}
  

Таким образом, внутренний цикл будет продолжаться вечно, и я застрял, пытаясь создать функцию для представления ее вычислительного времени. Я написал, что его время вычисления равно T (n) = [Суммирование i = 0 до (n-2)] (2 ^ j). 2^j представляет значение x с текущим значением j из внутреннего цикла. Обсудив это с моими коллегами, мы определенно согласны с тем, что время вычисления, безусловно, не зависит от значения n. Мы также могли бы полностью переосмыслить это, поскольку цикл бесконечен, и просто нет способа выразить его вычислительное время. Любая помощь очень ценится.

Сложность алгоритма определяется только для алгоритмов, которые по (наиболее часто принимаемому) определению должны завершаться. Этот процесс не завершается (за исключением «на практике», как отмечает Марсело; т. Е. Как программа на реальной машине против теоретически на теоретической машине Тьюринга с бесконечной лентой и все время в мире), так что это не алгоритм. Таким образом, у него нет «алгоритмической временной сложности».

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

Сложность большого O действительно бесконечного цикла не определена. Вот почему:

Определение для обозначения Big O гласит, что:

f(N) = O(g(N)) тогда и только тогда, когда f(n) <= |M g(n)| для некоторой константы M и для всех n >= n0

Однако обязательным условием является то, что f(n) и g(n) являются вещественнозначными функциями.

В случае бесконечного цикла гипотетическое значение времени, необходимого для завершения цикла, бесконечно. Таким образом, функция f(n) не будет сопоставляться N с действительным числом. Следовательно, f(N) не является вещественнозначной функцией, и мы не можем применить стандартное определение Big O таким образом, чтобы оно имело математический смысл.

(Страница Википедии в обозначении Big O содержит определение более формально, но результат тот же.)

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

(Однако мне не нравится это объяснение, поскольку оно основывается на конкретном определении термина «алгоритм». В вопросе фактически не используется этот термин.)

Ну, в реальном мире вы не получите ответа по очевидным причинам, но в математике… почему бы и нет.

Я запишу уравнение времени функции:

 T(n) = n-1 * T(X) 
  

T(X) — это время для внутреннего цикла. Я потрачу его: X1 = начальное значение x (в данном случае 1 )

 T(X) = T(X1 * 2)   1 = T(X1 * 4)   2 = ... = T(X1 * 2^j)   j
  

Конечным условием этого цикла является when j >= X1 * 2^j 1 , поэтому мы хотим решить:

 j >= X1 * 2^j -> j = 2^j -> j <= log2(j).
  

Приведенное выше уравнение не имеет решения в этом диапазоне набора натуральных чисел, но в наборе целых чисел оно легко решается с помощью -1 (фактически любого целого числа, меньшего 0 ).).

Таким образом, временная сложность для T(n) была бы (n-1) * (-1) = 1 - n .

Я не знаю, что в этом полезного, но я надеюсь, что это поможет вам.