Ожидаемого значения хода времени случайного алгоритма
Учитывая этот алгоритм, я обязано: Найти рекуррентную формулу ожидаемого значения времени работы. Найдите ближайшую верхнюю границу, насколько это возможно.
Я на самом деле немного потерял, так что если кто-то может помочь ...
Рекурсивной формула для наихудшего случая: T(n) = T(n/2) + n
Рекурсивной формула для лучшего случая: T(n) = T(1) + n
Рекурсивной формула для ожидаемого случая: T(n) = T(n/4) + n
Наихудший: 2n = O(n)
Лучший случай: n = O(n)
Ожидаемый случай: 4n/3 = O(n)
Некоторые люди здесь, кажется, запутались в log(n) фактор. log(n) будет требоваться только в том случае, если T(n) = 2T(n/2) + n, т. Е. Если функция была вызвана TWICE рекурсивно с половиной ввода.
Я понимаю, что вы сказали, и я подумал о чем-то подобном, мне нужно найти явная формула для ожидаемого значения времени выполнения, и это наиболее проблематичный момент. –
@BinyaminRiahi Извините, не уверен, что именно вы просите, когда говорите «явная формула ожидаемого значения времени выполнения». – wookie919
Это линейное время O (n) с точностью до множителя. – gongzhitaao
Где вы застряли, записывая рекурсивную формулу для ожидаемого времени работы? Это не так сложно записать, и, конечно, намного проще, чем фактически решить это! –
В качестве подсказки вы можете проверить анализ ожидаемого времени выполнения quickselect. Он не идентичен вашему алгоритму, но он имеет много общих черт, а рекурсивная формула и ее решение будут похожи. –