Complexité temporelle de cet algorithme

Question

J'ai fait quelques lectures sur la complexité temporelle, et j'ai les bases couvertes. Pour renforcer le concept, j'ai regardé une réponse que j'ai donnée récemment sur SO. La question est maintenant close, pour raison, mais ce n'est pas le but. Je n'arrive pas à comprendre quelle est la complexité de ma réponse, et la question était close avant que je puisse avoir un retour utile.

The task était de trouver le premier caractère unique dans une chaîne. Ma réponse était quelque chose de simple:

public String firstLonelyChar(String input) 
{ 
    while(input.length() > 0) 
    { 
     int curLength = input.length(); 
     String first = String.valueOf(input.charAt(0)); 
     input = input.replaceAll(first, ""); 
     if(input.length() == curLength - 1) 
      return first; 
    } 
    return null; 
} 

Link to an ideone example

Ma première pensée était que puisqu'il regarde chaque personnage, puis regarde à chaque fois pendant replaceAll(), il serait O (n^2).

Cependant, cela m'a fait penser à la façon dont cela fonctionne réellement. Pour chaque caractère examiné, il supprime toutes les occurrences de ce caractère dans la chaîne. Donc, n diminue constamment. Comment cela compte-t-il? Est-ce que cela fait O (log n), ou y a-t-il quelque chose que je ne vois pas?

Ce que je vous demande:

Quelle est la complexité temporelle de l'algorithme comme il est écrit, et pourquoi?

Ce que je ne demande pas:

Je ne cherche pas des suggestions pour l'améliorer. Je comprends qu'il y a probablement de meilleurs moyens de le faire. J'essaie de mieux comprendre le concept de complexité du temps, de ne pas trouver la meilleure solution.

Answer 1

La plus grande complexité de temps que vous aurez est pour la chaîne aabb... et ainsi de suite chaque cahracter répété exactement deux fois. Maintenant, cela dépend de la taille de votre alphabet, disons S. Annotons également la longueur de votre chaîne initiale avec L. Donc, pour chaque lettre, vous devrez parcourir toute la chaîne. Cependant, la première fois que vous faites cela, la chaîne sera de taille L, la deuxième fois L-2 et ainsi de suite. Dans l'ensemble, vous devrez effectuer dans l'ordre de L + (L-2) + ... + (L- S*2) opérations et c'est L*S - 2*S*(S+1), en supposant que L est plus de 2*S. En passant, si la taille de votre alphabet est constante, et je suppose que c'est le cas, la complexité de votre code est O(L) (mais avec une grande constante).

Answer 2

Le pire des cas est O(n^2) où n est la longueur de la chaîne d'entrée. Imaginez le cas où chaque personnage est doublé sauf le dernier, comme "aabbccddeeffg". Ensuite, il y a n/2 itérations de boucle, et chaque appel à replaceAll doit balayer toute la chaîne restante, qui est également proportionnelle à n. Editer: Comme le souligne Ivaylo, si la taille de votre alphabet est constante, c'est techniquement O(n) puisque vous n'envisagez jamais un personnage plus d'une fois.

Answer 3

la marque Let:

m = nombre de lettres uniques dans le mot
n = longueur d'entrée

Ceci est le calcul de la complexité:
La boucle principale passe au plus m fois, parce qu'il y a m lettres différentes, le .Replaceall vérifie au plus O (n) comparaisons dans chaque cycle.

le total est: O (m * n) du cycle

un exemple de O (m * n) est la suivante: entrée = aabbccdd,

m = 4, n = 8

les étapes de l'algorithme:

1. input = aabbccdd, complex - 8 
2. input = bbccdd, complex = 6 
3. input = ccdd, complex = 4 
4. input = dd, complex = 2 

total = 6 + 8 + 4 + 2 = 20 = O (m * n)

Answer 4

Soit m soit la taille de votre alphabet, et laissez n la longueur de votre chaîne. Le pire serait de répartir uniformément les caractères de votre chaîne entre les lettres de l'alphabet, ce qui signifie que vous aurez n/m caractères pour chaque lettre de votre alphabet, marquons cette quantité avec q. Par exemple, la chaîne aabbccddeeffgghh est la distribution uniforme de 16 caractères entre les lettres a-h, alors ici n=16 et m=8 et vous avez q=2 caractères pour chaque lettre. Maintenant, votre algorithme passe réellement les lettres de l'alphabet (il utilise juste l'ordre dans lequel elles apparaissent dans la chaîne), et pour chaque itération il doit aller sur la longueur de la chaîne (n) et rétrécir par q (n -= q). Ainsi, sur tout le nombre d'opérations que vous faites dans le pire des cas sont:

s = n + n-(1*q) + ... + n-((m-1)*q) 

Vous pouvez voir que s est la somme des premiers m éléments de la série arithmétique:

s = (n + n-((m-1)*q) * m/2 = 
    (n + n-((m-1)*(n/m)) * m/2 ~ n * m/2