Время вычисления T (n) и Big-O с бесконечным циклом

Question

Я запутался в том, как создать функцию 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. Мы также могли бы полностью обдумать это, поскольку цикл бесконечен, и просто нет способа выразить его вычислительное время. Любая помощь с благодарностью.

Answer 1

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

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

Answer 2

Сложность Big-O подлинно бесконечного цикла равна undefined . И вот почему:

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

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

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

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

(Страница Википедии на Big O Notation гласит это более формально.)

Answer 3

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

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

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

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

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

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

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

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