Среднего случай Сложности тривиального алгоритма

P(x,y,z){ 
    print x 
    if(y!=x) print y 
    if(z!=x && z!=y) print z 
}

Trivial Алгоритм здесь, значение x, y, z выбираются случайным образом из {1,...r} с r >= 1. Я пытаюсь определить среднюю сложность этого алгоритма, и я измеряю сложность, основанную на количестве операторов печати.Среднего случай Сложности тривиального алгоритма

Наилучшим случаем здесь является T (n) = 1 или O (1), когда x=y=z и вероятность того, что это 1/3.
В худшем случае все еще T (n) = 3 или еще O (1), когда x!=y!=z, а вероятность равна 2/3.

Но когда дело доходит до математически получения среднего случай:
Sample Пространство п возможные входы, Вероятность над выборочным пространством является 1/п шанс Итак, как рассчитать среднюю сложность дела? (Здесь я рисую пробел ..)

источник

2012-05-20 Anonymous

Ваш алгоритм имеет три случая:

Все три числа равны. Вероятность этого составляет 1/г, так как только вы выбираете х, есть только один выбор для у и г. Стоимость для этого случая 1.
х! = У, но х == г или у == г. Вероятность этого равна 1/r * (1/(r - 1)) * 1/2, , так как вы выберете x, у вас останется только r -1 для y, а z может быть только один из этих два варианта. Стоимость = 2.
Все три цифры различны. Вероятность того, что все три разные, равна 1/r * (1/(r - 1)) * (1/(r - 2)). Стоимость = 3.

Таким образом, средний случай может быть вычислена как:

1/r + 1/r * (1/(r - 1)) + 1/r * (1/(r - 1))*(1/(r - 2)) * 3 == O(1)

Edit: выше выражение O (1), так как все выражение состоит из констант.

источник

2012-05-21 12:48:18 rrufai

Я знаю, что сложность должна быть O (1), но как вы прибудете при этом из уравнения выше? –

@spacker_lechuck: Все выражение состоит из констант. Вот почему это O (1). – rrufai

ohhhhhhh Я вижу сейчас, спасибо! –

Средний случай будет где-то между лучшими и худшими случаями; для этой конкретной проблемы, это все, что вам нужно (по крайней мере, до большого-O).

источник

2012-05-20 23:36:27

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

2) Если можно, то запустите моделирование monte carlo и нарисуйте результаты. то есть для N = 1, 5, 10, 20, ..., 100, 1000 или любого другого образца реалистично, прогоните 10000 проб и рассчитайте среднее время. Если вам повезло, X = размер выборки, Y = avg. время для 10000 пробегов при этом размере выборки будет отображать красивую линию, или параболу, или некоторую легко-модельную кривую.

Поэтому я не уверен, нужна ли вам помощь (1) найти или кодировать алгоритм или (2) проанализировать его, вы, вероятно, захотите пересмотреть свой вопрос, чтобы указать это.

источник

2012-05-21 00:50:32 djechlin

P(x,y,z){ 
    1.print x 
    2.if(y!=x) 
    3. print y 
    4.if(z!=x && z!=y) 
    5. print z 
}

Линия 1: принимает постоянное время c1 (c1: печать х)

Линия 2: принимает постоянное время c2 (c2: состояние тест)

Линия 3: занимает постоянное время c3 (с3: печать у)

линия 3: принимает постоянное время c4 (с4: C ondition тест)

Линия 4: принимает постоянное время c5 (c5: печать г)

Анализ:

Если ваша функция Р (х, у, г) не зависит не от входной размер «r», программа будет принимать постоянное количество времени для запуска с . С учетом времени: T (c1) + T (c2 + c3) + T (c4 + c5) .. суммируя большую функцию O P (x, y, z) равно O (1) где 1 - постоянная величина и указывает постоянное время, так как T (c1), T (c2), .. T (c5) все принимают постоянную количество времени ... и скажем, если функция P (x, y, z) повторяется от 1 до r..если сложность вашего фрагмента изменилась бы и будет соответствовать размеру ввода, то есть «r»

Лучший случай: O (1)

Средний Корпус: O (1)

худший случай: O (1)

источник

2013-11-19 09:50:57

Среднего случай Сложности тривиального алгоритма

ответ

Смежные вопросы