Je travaille avec un algorithme de division et de conquête très spécifique qui divise toujours un problème avec n éléments en deux sous-problèmes avec les éléments n/2 - 1 et n/2 + 1.Complexité temporelle pour un algorithme de division et de conquête créant deux sous-problèmes inégaux.
Je suis assez sûr que la complexité du temps reste O (n log n), mais je me demande comment je pourrais le prouver formellement.
Prenez le « travail utile » à chaque niveau de récursivité être une fonction f(n):
Observons ce qui se passe quand nous substituons à plusieurs reprises ce retour sur lui-même.
T(n) termes:
spot le modèle?
à la profondeur de récursivité m:
appels récursifs à TT est 
à 
, dans les étapes de 
Ainsi, la somme de tous les T -termes à chaque niveau est donné par:
f(n) termes:
Regardez familier?
Les f(n) termes sont exactement un niveau de récursivité derrière les termes T(n). Par conséquent adapter l'expression précédente, nous arrivons à la somme suivante:
noter toutefois que nous commençons seulement unf -TERM, cette somme a un cas limite invalide. Cependant, ceci est simple à rectifier - le résultat du cas spécial pour m = 1 est simplement f(n).
La combinaison de ce qui précède, et en additionnant les f termes pour chaque niveau de récursivité, nous arrivons à la (presque) expression finale pour T(n):
Nous avons besoin prochain pour trouver quand la première sommation pour T -terms se termine. Supposons que c'est quand n ≤ c.
Le dernier appel à mettre fin a intuitivement le plus grand argument-à-dire l'appel à:
Par conséquent, l'expression finale est donnée par:
Retour au problème original, quelle est f(n)?
Vous n'avez pas indiqué ce que c'est, donc je ne peux que supposer que la quantité de travail effectué par appel est ϴ(n) (proportionnelle à la longueur du tableau). Ainsi:
Votre hypothèse était correcte.
Notez que même si nous avions quelque chose de plus général comme
Où a est une constante pas égale à 1, nous aurions encore ont ϴ(n log n) à la suite, étant donné que les termes 
dans l'équation ci-dessus annulent:
J'ai finalement compris. Merci! Que faire si la quantité de travail effectuée est log (n), au lieu de n (comme chercher dans un tableau ordonné)? Je suppose que la complexité tombe à O (n). Comment ajuster la partie finale de la preuve? –
Remplacer 'f (n)' par 'log (n)'. Cependant, la solution devient non triviale, nous pouvons donc avoir besoin de faire quelques approximations pour arriver à une réponse finale. – meowgoesthedog