[Algoritmi] dalla definizione di O dimostrare che...

[mathix1]

ho questo esercizio, e sinceramente non so dove sbattere la testa visto che sul libro di testo non c'è un minimo accenno a come fare ciò, la traccia è:

dalla definizione di O dimostrare che T(n) = O(nlogn)

allora la definizione dice che:
T(n) = O(f(n)) se esistono due costanti positive c e n0 tali che n>n0 risulti T(n)< c f(n)

io con questa definizione come faccio a dimostrare che t(n) = O(nlogn) ?
qualche consiglio?

[hamming_burst]

Ciao,
devi applicare la dimostrazione per induzione.

esempio: ricorrenze-e-domande-t80600.html (segui la ricorrenza: [tex]T(n)=4T(n/5)+T(n/6)+n[/tex])

se non sai cos'è l'induzione: (apatriarca) post555494.html#p555494 o (Deckard) ricorrenza-soluzione-corretta-t81528.html

prova ad applicare ciò e ne riparliamo

PS: che libro usi? come fa a non esserci una cosa basilare come questa?

[mathix1]

come libro di testo il docente ci ha fatto usare un pdf gratuito di 150 pagine, ma da quanto ho visto non è molto completo.

che ne dici se studio sul cormen (introduzione ad algoritmi e strutture dati 2ed)?

[mathix1]

Vediamo se ho capito:

partendo da T(n) < c f(n) devo dimostrare T(n)= O(n logn)
quindi T(n) < cnlogn
per c >= 1
T(n) = nlogn

assumendo che valga per n/2 abbiamo che
T(n) = c(n/2)log(n/2)
T(n) = c(n/2)logn - clog2 (log2 vale 1)
T(n) = c(n/2)logn - c

per c =1 abbiamo

T(n) = (n/2)logn - 1, ignoriamo la costante 1
T(n) = O(nlogn)

giusto?

il problema è che non ho un'equazione iniziale come in tutti gli esercizi che ho visto nei link che mi hai postato

[apatriarca]

Ma senza dati più specifici l'unica cosa da dire è che devi dimostrare che valga la dimostrazione. Non c'è molto altro da dire. Le cose si fanno interessanti solo quando si inizia a lavorare con problemi concreti e si rende quindi necessario l'utilizzo di particolari strumenti di dimostrazione.

[mathix1]

"apatriarca":Ma senza dati più specifici l'unica cosa da dire è che devi dimostrare che valga la dimostrazione. Non c'è molto altro da dire. Le cose si fanno interessanti solo quando si inizia a lavorare con problemi concreti e si rende quindi necessario l'utilizzo di particolari strumenti di dimostrazione.

quindi ciò che ho scritto nel post su ha un senso? senno che mi consigli di scrivere?

[hamming_burst]

quello che ti dice sensatamente apatriarca è che quello che cerchi di dimostrare è di una funzione generica.
Cioè che una qualche funzione $f(n) <= cnlogn$.
$f(n)$ è qualunque cosa, pensavo che non la avessi riportata perchè sapevi questo

te metti $n/2$ perchè hai un'equazione di ricorrenza della forma $T(n/2) + g(n)$?. Cioè cos'è per te $T(n)$?
Quello che ti cerca di dire, che se non ha qualcosa di particolare come un'equazione di ricorrenza, ciò che dimostrati ha poco significato, se non quello di poterti dire che sai usare la tecnica di induzione o meno

[mathix1]

purtroppo T(n) non è specificato. questo è un'esercizio uscito all'esame, chiedeva di far riferimento alla definizione di grande O e dimostrare quella li, non c'era scritto altro

[apatriarca]

Il problema è che la richiesta non ha senso. Non c'è infatti niente da dimostrare, mancano completamente le ipotesi e la natura della proposizione \(T(n) \in O(n \log n)\) dipende dalla natura di \(T(n)\). Sei certo che ci fosse scritto solo questo? Sei certo che \(T(n)\) non fosse ad esempio definito in qualche punto precedente?