Правильны ли обозначения Big-O для следующих программ? - PullRequest
Новая
       16

Правильны ли обозначения Big-O для следующих программ?

0 голосов
/ 08 апреля 2019

У меня есть следующие три программы, и я рассчитал сложность времени Big-O для каждой из них.Я просто хочу убедиться, что все сделал правильно. 

import random

def A(N):

      L=[]

      for i in range(0,26):
            L.append(chr(ord('A')+i))
      Alpha=[]
      i = 0
      while i< N:
            flag = 0
            x = random.randint(0,N-1)
            for j in range(0,i):
                  if Alpha[j] == L[x]:
                        flag = 1
                        break

            if flag == 0:
                  Alpha.append(L[x])
                  i = i + 1
      return Alpha

Сложность для A (N) равна [O (1) + O (n) + O (n)] ->O (n ^ 2) 

def A2(N):

      L=[]

      x = ord('A')
      for i in range(0,26):
            L.append(chr(x+i))
      Alpha=[]
      i = 0
      Ran = [0]*N
      while i< N:
            x = random.randint(0,N-1)
            if Ran[x] == 0 :
                  Alpha.append(L[x])
                  i=i+1
                  Ran[x]=1
      return Alpha

Сложность для A2 (N) составляет [O (1) + O (n)] -> O (n) 

def A3(N):

      L=[]

      x = ord('A')
      for i in range(0,26):
            L.append(chr(x+i))
      Alpha=[]
      for i in range(0,N):
            Alpha.append(L[i])
      for i in range(2,N):
            x= random.randint(0,i)
            temp = Alpha[i]
            Alpha[i]= Alpha[x]
            Alpha[x] = temp
      return Alpha

Сложность для A3 (N) составляет [O (1) + O (n) + O (n)] -> O (n ^ 2)

Ответы [ 3 ]

4 голосов
/ 08 апреля 2019

В первом примере сложность составляет , а не

[O (1) + O (n) + O (n)] -> O (n ^ 2)

но это [O (1) + сумма от i = 0 до O (n) из [O (n)]] * = сумма от i = 0 до O (n) из [O ( n)] = O (n ^ 2)

На практике вы выполняете задачу O (n) максимум n раз - следовательно, O (n) раз. Вот почему это, по сути, умножение.

Во втором примере вы были бы правы, если бы выполнение цикла не зависело от случайных чисел - спасибо Нику Витха за указание на это, см. его ответ - но, к сожалению, это так.

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

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

В третьем примере 1042 * это действительно :

[O (1) + O (n) + O (n)]

но когда вы добавляете сходные классы вместе, вы получаете один и тот же класс сложности по времени - это потому, что вы получили бы кратность начальной сложности, которая в асимптотическом контексте равна ей. Таким образом, решение будет:

[O (1) + O (n) + O (n)] -> O (n)

Я прошу прощения, если, говоря математически, моя запись не является точной, но я считаю, что она достаточно обобщает концепцию.

0 голосов
/ 09 апреля 2019

Для А2 я согласен с Ником, что он неограничен (наихудший случай).Ваш средний случай - n * Log (n).Ваш O (n) на самом деле лучший случай.

0 голосов
/ 08 апреля 2019

1.

Сложность для A (N) составляет [O (1) + O (n) + O (n)] -> O (n ^ 2)

Это не правильно.Ну, часть O (n ^ 2) верна, но то, как вы к ней пришли, не соответствует действительности.

[O (1) + O (n) + O (n)] -> O (2n +)1) -> O (n)

Однако ваш код:

[O (k) + O (n) * O (n)] -> O (n^ 2 + k) -> O (n ^ 2)

, где k - это константа (в данном случае 26, но это не имеет значения, если на нее не влияет n).Вы умножаете вещи, которые так вложены.Вы можете упростить O (k) до O (1), если хотите.В любом случае это уходит.

2.

Сложность для A2 (N): [O (1) + O (n)] -> O (n)

О, боже.Я даже не уверен, с чего начать.

Итак, в основном вы получаете доступ к случайной части массива длиной N.И вы проверяете, равно ли это 0. Если это так, вы делаете некоторые вещи и присваиваете их 1. 1. 1030 *

Я склонен полагать, что ответ на это будет значительно выше, чем O (n) насредний.Кто-то, у кого было больше опыта в кофе и / или математике, вероятно, должен будет вмешаться в это, но вы собираетесь пройти по крайней мере n раз, и В МИРЕ этот цикл будет бесконечным, потому что вы делаете произвольный доступ и можете просто сохранитьслучайным образом проверяя число, равное 1. Обычно вы делаете запись O (), используя WORST, поэтому этот цикл имеет вид

O (бесконечность) -> undefined

3.

Сложность для A3 (N) составляет [O (1) + O (n) + O (n)] -> O (n ^ 2)

Asкак было сказано ранее, это равно [O (1) + O (n) + O (n)], но это дает O (n)

...