Quel est le temps de trouver un maximum récursivement

Je voulais juste m'assurer que je vais dans la bonne direction. Je veux trouver une valeur maximale d'un tableau en le divisant récursivement et trouver le maximum de chaque tableau séparé. Parce que je le divise, ce serait 2 * T (n/2). Et parce que je dois faire une comparaison à la fin pour les 2 tableaux, j'ai T (1). voilà ce que ma relation de récurrence comme ceci:Quel est le temps de trouver un maximum récursivement

T = {2 * T (n/2) + 1, lorsque n> = 2; T (1), lorsque n = 1;

et donc ma complexité serait Theta (nlgn)?

Source

2011-04-26 Dan

La formule que vous avez composée semble correcte, mais votre analyse n'est pas parfaite.

T = 2*T(n/2) + 1 = 2*(2*T(n/4) + 1) + 1 = ...

Pour le i-ième itération vous obtiendrez:

Ti(n) = 2^i*T(n/2^i) + i

maintenant ce que vous voulez savoir pour que je ne n/2^i est égal à 1 (ou à peu près tout constant, si vous aimez) afin que vous atteigniez la condition finale de n = 1. Ce serait la solution à n/2^I = 1 -> I = Log2 (n). Plante dans l'équation de Ti et vous obtenez:

TI(n) = 2^log2(n)*T(n/2^log2(n)) + log2(n) = n*1+log2(n) = n + log2(n)

et vous obtenez T (n) = O (n + log2 (n) (comme @bdares dit) = O (n) (comme @ bdares dit)

Source

2011-04-26 09:15:20 Neowizard

merci pour la clarification – Dan

Est-il normal d'écrire O (n + log (n))? On dirait que O (n) suffirait, dans * chaque * événement. En fait, pourquoi soft-ball dans comme ça? J'ai l'impression d'écrire O (n + log (n)), même si ce n'est pas faux, c'est bête. Nous n'écrivons pas O (n^2 + n) pour Bubblesort. Est-ce que je manque quelque chose? Si vous utilisez juste cela à des fins d'illustration, OK; Je suppose que c'est un peu bizarre pour moi de ne pas voir la dernière étape réalisée ... alors si c'est le cas, prenez cela comme une critique du style, pas du contenu. – Patrick87

@bdares Vous avez raison. J'aurais dû ajouter la dernière étape. J'évite de sauter la partie (n + log (n)) quand je l'explique pour éviter toute confusion, mais je devrais m'assurer d'ajouter la dernière partie aussi. – Neowizard

Non, non ... vous prenez le temps O (1) pour chaque récursion.

Combien en a-t-il?

Il y a N feuilles, donc vous savez qu'il s'agit au moins de O (N).

Combien avez-vous besoin de comparer pour trouver le maximum absolu? C'est O (log (N)).

Ajoutez-les ensemble, ne les multipliez pas. O (N + log (N)) est la complexité de votre temps.

Source

2011-04-26 08:51:11 bdares

oh je vois .j'étais plutôt confus parce que ça ressemblait à fusionner le tri.est donc la relation de récurrence à droite ou à faux aussi? – Dan

Eh .. je suis vraiment floue sur ça, mais ça a l'air juste. le niveau ajoutera 1, puis 2, puis 4, puis 8, et ainsi de suite ... donc je me suis trompé Il faudra 1 + 2 + 4 + 8 + ... + 2^log (n) temps pour chaque étape , et prendra donc O (2 * n) temps, qui est O (n) temps Incidemment, le même que O (N + log (N)) qui est aussi O (n), mais la première explication était fausse – bdares

Quel est le temps de trouver un maximum récursivement

Répondre

Questions connexes