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

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

e.g:

{
define (some-recursive-function)

    x = (random in range of 1 to 100000);
    if (x == 10)
    {
        return "this function has terminated";
    }
    else
    {
        (some-recursive-function)
    }
}

Я понимаю, что для бесконечных циклов не будет определена сложность. Как насчет некоторых функций, которые определенно завершаются, но через неизвестное количество времени?

Было бы хорошо найти среднюю временную сложность для этого. Как можно найти временную сложность в худшем случае, если она существует?

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

РЕДАКТИРОВАТЬ: Как уже отмечалось, я полностью упустил тот факт, что для этой функции нет ввода. Вместо этого предположим, что у нас есть:

{define (some-recursive-function n)

    x = (random in range of 1 to n);
    if (x == 10)
    {
        return "this function has terminated";
    }
    else
    {
        (some-recursive-function)
    }
}

Изменит ли это что-нибудь?


algorithm time-complexity complexity-theory asymptotic-complexity
person Evan Li    schedule 26.10.2017    source источник
comment
Было бы сложно найти сложность формы O (f (n)), учитывая, что здесь нет n   -  person Leeor    schedule 26.10.2017
comment
en.wikipedia.org/wiki/Bogosort в худшем случае неограничен. Использует случайные числа для сортировки.   -  person Caramiriel    schedule 26.10.2017
comment
Разве худший случай не бесконечен? Нет никакой гарантии, что данное число в диапазоне будет выбрано случайным образом.   -  person Moop    schedule 26.10.2017
comment
Вы хотели передать n в своем рекурсивном вызове или x?   -  person Jim Mischel    schedule 27.10.2017
comment
@Moop на самом деле есть, по крайней мере теоретически - каждое число в диапазоне должно иметь одинаковую вероятность, а это означает, что если ГСЧ сгенерировал какое-то число - через некоторое время он сгенерирует любое другое число в диапазоне   -  person Iłya Bursov    schedule 27.10.2017
comment
@IlyaBursov Это еще не гарантия, просто очень маловероятно. Наихудший случай означает наихудший случай, это означает, что бедняжке 10 никогда не звонят.   -  person Moop    schedule 27.10.2017
comment
@Moop обычно мы говорим о равномерном распределении, которое гарантирует, что даже в худшем случае мы получим все числа через некоторое время ... возможно, долгое время   -  person Iłya Bursov    schedule 27.10.2017
comment
@IlyaBursov Даже при равномерном распределении нет гарантии, что будет выбрано любое число, даже если оно будет продлено до конца времени. Крайне маловероятно, но это не то же самое, что гарантия. Подумайте даже о простом подбрасывании монеты. Нет никаких гарантий, что в какой-то момент вам выпадет орёл. Конечно, крайне маловероятно, что после нескольких испытаний никогда не выпадет решка, но все же это возможно.   -  person Moop    schedule 27.10.2017
comment
Совокупная вероятность @Moop получить один конкретный результат из конечного набора абсолютно сходится к 1, конечно, с бесконечным числом бросков   -  person Iłya Bursov    schedule 27.10.2017

Ответы (2)


arrow_upward
0
arrow_downward

Если нет функции от n, которая ограничивает время выполнения функции сверху, то верхней границы времени выполнения просто нет. В зависимости от случая может быть нижняя граница времени выполнения. Мы также можем говорить об ожидаемом времени выполнения и даже накладывать ограничения на ожидаемое время выполнения, но это отличается, с одной стороны, от ограничений в среднем случае, а с другой стороны, от ограничений самого времени выполнения.

Как сейчас написано, когда n меньше 10, вообще нет границ: функция просто не завершается ни при каком событии. Для n >= 10 по-прежнему нет верхней границы ни в одном из случаев — это может занять сколь угодно много времени, — но нижняя граница в любом случае является линейной (вы должны хотя бы прочитать значение n, которое состоит из N = потолочных (log n) битов; ваш метод выбора случайного числа, не превышающего n, может потребовать дополнительного времени и/или места). Поведение случая здесь довольно неинтересно.

Если мы рассмотрим ожидаемое время выполнения функции с точки зрения значения (а не длины) входных данных, мы увидим, что существует вероятность 1/n того, что любой конкретный вызов выберет правильное случайное число (опять же, для n >= 10) ; мы понимаем, что количество раз, которое нам нужно попытаться получить, задается геометрическим распределением и что математическое ожидание равно 1/(1/n) = n. Таким образом, ожидаемая глубина рекурсии является линейной функцией значения входных данных n и, следовательно, экспоненциальной функцией размера входных данных N = log n. Мы восстанавливаем точное выражение для ожидания; поэтому верхняя и нижняя границы также являются линейными, и это охватывает все случаи (лучший, худший, средний и т. д.). Я говорю о глубине рекурсии, поскольку среда выполнения также будет иметь дополнительный коэффициент N = log n или более из-за к замечанию в предыдущем абзаце.

person Patrick87    schedule 26.10.2017

arrow_upward
-1
arrow_downward

Вам нужно знать, что существуют «простые» формулы для расчета сложности рекурсивного алгоритма, используя, конечно, повторение.

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

Я поставлю этот вопрос/ответ для большего удобства:

Определение сложности рекурсивных функций (нотация Big O)

person M.K    schedule 26.10.2017