J'ai les suivants suivis:
T(n) = T(n - 1) + n = O(n^2)
4 Réponses :
Vous avez également besoin d'un cas de base pour votre relation de récurrence.
T(1) = 1: * T(2) = 3: * ** T(3) = 6: * ** *** T(4) = 10: * ** *** **** etc..
Pourriez-vous me dire comment vous êtes arrivé à la troisième équation que vous avez dans votre réponse? Quelle technique mathématique avez-vous appliquée?
@ Syton: C'est une "supposition". En réalité, c'est parce que je connais la formule pour les nombres triangulaires - je ne l'ai pas dit, je le connaissais déjà. Il est souvent plus facile de "deviner" la bonne réponse et prouve qu'il est correct au lieu de le dériver des premiers principes. Il s'agit d'une technique standard pour la résolution des relations de récurrence.
@Tony: Le terme technique pour une supposition éduquée est "Ansatz". Voir: EN.Wikipedia.org/wiki/ansatz . Il y a des informations sur l'utilisation d'une supposition pour résoudre une relation de récurrence dans Wikipedia: en.wikipedia.org/wiki/ Récurrence_relation . D'autres méthodes possibles de résolution de relations de récurrence sont également énumérées là-bas.
De O (N ^ 2), vous pouvez plus facilement deviner que la solution exacte est une hache polynomiale quadratique ^ 2 + bx + C et résoudre pour A, B et C. Il y a une description détaillée Comment résoudre ces problèmes dans le livre de livres en mathématiques en béton par Knuth, Oren, PataShnik.
regarde à peu près à droite, mais dépendra de l'affaire de base T (1). En supposant que vous ferez des étapes pour obtenir T (n) à t (0) et chaque fois que le terme N est entre 0 et N pour une moyenne de N / 2 SO N * N / 2 = (N ^ 2) / 2 = O (n ^ 2).
pense à cela de cette façon:
Dans chaque "itération" de la récursion, vous faites O (n) travail.
Chaque itération a du travail N-1 à faire, jusqu'à n = cas de base. (Je suppose que le cas de base est O (n) travail)
Par conséquent, supposer que le cas de base est un indépendant constant de N, il y a o (n) itérations de la récursivité.
Si vous avez n itérations de O (n) Travaillez chacun, O (n) * O (n) = O (n ^ 2).
Votre analyse est correcte. Si vous souhaitez plus d'informations sur cette façon de résoudre des récursions, examinez les arbres de récursion. Ils sont très intuitifs par rapport aux autres méthodes.
J'étais trop dans le calcul de tout ce que je pense et j'ai oublié le fait que nous traitons avec une récursion. Peut-être que c'est pourquoi je ne l'obtiens pas tout à fait. Pour ce qui précède, j'ai eu t (n) <= 2n serait-ce correct?
N'a pas bien compris ce que vous demandez, il y a beaucoup plus haut
@Tony: Non ce n'est pas correct. T (n) peut être supérieur à 2n pour la petite n.
La solution est assez facile pour celle-ci. Vous devez dérouler la récursion:
T(n) = T(n-1) + n = T(n-2) + (n - 1) + n = = T(n-3) + (n-2) + (n-1) + n = ... = = T(0) + 1 + 2 + ... + (n-1) + n
Je vote pour fermer cette question comme hors-sujet car c'est une question de mathématiques, pas une question de programmation.