Эквивалентность 2 простых частей псевдокода - PullRequest
Новая
       1

Эквивалентность 2 простых частей псевдокода

0 голосов
/ 25 февраля 2011

Я должен реализовать алгоритм, в котором способ, которым я придумал это на бумаге, немного отличается от псевдокода, предложенного в нашем учебнике.Я пытаюсь убедить себя в том, что 2 фрагмента псевдо ниже будут делать то же самое без каких-либо существенных различий в порядке сложности времени, когда приходится реализовывать «содержит» и генерировать все подмножества соответственно в два и один ниже.Я испытываю затруднения, придумывая что-то строгое, что убедит меня.

T и A - это наборы подмножеств конечного набора I. Ни один набор или подмножество не пусто, и каждый набор имеет "поле", называемое 'count'.

Фрагмент первый: 

For-each t in T do {
  A_t = A intersected with the set of all non-empty subsets of t
  For-each a in A_t do {
    a.count++
  }
}

Фрагмент второй: 

For-each a in A do {
  a.count = count(a, T)
}

Здесь количество определяется как 

count(a, T) {
  c = 0
  For-each t in T do {
    if (t contains a) {
      c++
    }
return c
}

1 Ответ

1 голос
/ 26 февраля 2011

Это зависит от того, как вы реализуете генерацию подмножества и содержит функцию.Я предполагаю, что в большинстве случаев генерировать все эти подмножества не стоит и (поскольку a находится в A_t, если a находится в A и в наборе подмножеств t, то есть a находится в A_t если a находится в A и t содержит a) вы можете просто переписать свой первый фрагмент в 

For-each t in T do {
  For-each a in A do {
    if (t contains a){
      a.count++
    }
  }
}

, в то время как ваш второй фрагмент - 

For-each a in A do {
  For-each t in T do {
    if (t contains a){
      a.count++
    }
  }
}

(в обоих случаях предполагается, что для всех a в A, a.count изначально установлено в 0)

...