Ricorrenza Relation T (n) = T (3/4 * n) + O (1)

Question

sto lavorando fuori la relazione di ricorrenza

T(n) = T(3/4 * n) + O(1)

E 'venuta fuori per essere O(log(n)), ma mi è stato detto prima mano che la soluzione è O(n). Non riesco a trovare dove sto andando male - questo sembra proprio come la relazione di ricorrenza per la ricerca binaria. Qualche suggerimento?

Answer 1

Provate a sostituire T(n) = c*n o T(n) = c * log n nell'equazione e solving. Una delle due equazioni saranno risolvibili.

È possibile anche controllare la tua risposta valutando la funzione per diversi valori di n.

-- Define T in your preferred language
t n | n <= 1 = 1 | otherwise = t (3/4 * n) + 1

-- If it's O(log n), then T(n)/log(n) should be asymptotically constant
-- If it's O(n), then T(n)/n should be asymptotically constant
check1 n = t n / log n
check2 n = t n / n

print [check1 1e10, check1 1e11, check1 1e12, check1 1e13]
print [check2 1e10, check2 1e11, check2 1e12, check2 1e13]

Uno di questi sarà convergere ad un piccolo numero positivo, l'altro andrà a zero o infinito.

Answer 2

T (n) = T (3/4 * n) + O (1) ............... (1) supra eq. T (3/4 * n) è sconosciuto termine se ti stai chiedendo circa la soluzione di questa ricorrenza, allora voglio dire che siamo in grado di risolvere questo eq. utilizzando il metodo di sostituzione. in questo dobbiamo scoprire il valore di T (3n / 4) dalla eq principale. e sostituire in eq. in modo ricorsivo. Poiché questa ricorrenza è dipende dalla ricorsione. n = 3n / 4 T (3n / 4) = T ((3/4) ^ 2 * n) + c ............... (2) notazione O sostituito da costante c. ora sostituire T (3n / 4) a (1) T (n) = T ((3/4) ^ 2 * n) + 2c ................ (3) ora mettere n = ((3/4) ^ 2 * n) a (1) T ((3/4) ^ 2 * n) = T ((3/4) ^ 3 * n) + c Sostituto T (n) = T ((3/4) ^ 3 * n) + 3c ............... (4)

Dopo il passo KTH eq. sarà T (n) = T ((3/4) ^ k * n) + kc ................ (5) in questo passaggio n sarà 2 o 1 (grandezza ingresso ) (3/4) ^ k * n = 1 n = (4/3) ^ k prendendo registro su entrambi i lati. log (n) = k * log (4/3) k = log (n) .............. valore posto in eq. (5) T (n) = T (1) + log (n) * C .............. (6) T (n) = O (log n)

Answer 3

Le risposte che vengono date non vengono visualizzati il ??modo corretto di risolvere questo genere di ricorrenze. È caso è facilmente risolvibile con un teorema principale e nel tuo caso a=1 e b=4/3. Ciò significa che c = logb(a) = 0.

Perché il vostro f(n) è una costante, si cade nel secondo caso secchio e dove k=0. Quindi la soluzione è , dove c = 0 e k = 0. Ciò significa che:

---

O(log(n)) è una risposta corretta