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

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

Здесь используется тривиальный алгоритм, значения 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.

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


average algorithm time-complexity big-o
person Community    schedule 20.05.2012    source источник

Ответы (4)


arrow_upward
1
arrow_downward

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

  1. Все три числа равны. Вероятность этого составляет 1/r, поскольку после выбора x есть только один выбор для y и для z. Стоимость данного случая 1.
  2. x != y, но x == z или y == z. Вероятность этого равна 1/r * (1/(r - 1))* 1/2, поскольку, как только вы выберете x, у вас останется только r -1 вариантов выбора для y, а z может быть только одним из этих двух вариантов. . Стоимость = 2.
  3. Все три числа различны. Вероятность того, что все три различны, равна 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)

Изменить: приведенное выше выражение равно O(1), поскольку все выражение состоит из констант.

person rrufai    schedule 21.05.2012
comment
Я знаю, что сложность должна быть O(1), но как вы пришли к этому из приведенного выше уравнения? - person ; 23.05.2012
comment
@spacker_lechuck: все выражение состоит из констант. Вот почему это O (1). - person rrufai; 23.05.2012

arrow_upward
0
arrow_downward

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

person Scott Hunter    schedule 20.05.2012

arrow_upward
0
arrow_downward

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

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

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

person djechlin    schedule 21.05.2012

arrow_upward
0
arrow_downward 

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:print x)

Строка 2: занимает постоянное время c2 (c2:условный тест)

Строка 3: занимает постоянное время c3 (c3 :print y)

Строка 3: занимает постоянное время c4 (c4:условный тест)

Строка 4: занимает постоянное время c5 (c5:print z)

Анализ:

Если ваша функция P(x,y,z) не зависит от размера входных данных " r", программе потребуется постоянное количество времени для выполнения, поскольку Time Taken :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)

person Diljit PR    schedule 19.11.2013