Algo trop lent :(

Question

Bon tout d'abord je tient à préciser qu'il s'agit du concours prologin auquel je compte participer donc si certaines personnes ne veulent pas m'aider je comprendrais..
Mais je ne demande aucune réponse je veux simplmenet une explication histoire de comprendre ce qui ne vas pas..
Voila mon algo ne passe pas les test de vitesse il faut en fait trouver le nombre de chaine faisable qui commence par a et qui finit par b (par ex abab renvoie 3 : le 1er ab puis abab pui le second ab)

Voila mon prog svp expliker moi en quoi c'est trop lent ; meme une aide anodine serait précieuse !! merci ^^

#include <stdio.h>

int sousChaineAB(char* tab, int size)
{

int chaine = 0;

        for (int i=0;i<size;i++)
        {

            if (tab[i] == 'a')
            {

              for(int j=i+1;j<size;j++)
                      {
                       if (tab[j]== 'b')
                          chaine++;

                       }

            }

        }
          return chaine;
}

int main()
{
   int size, i;
   char tab[1000000];
   scanf("%d", &size);
   for (i = 0; i < size; i++)
   {
      do
         scanf("%c", &(tab[i]));
      while ((tab[i] == '
') || (tab[i] == ''));
   }
   printf("%d
", sousChaineAB(tab, size));

 }

cosmobob · Answer

ton algo est trop lent car dans le cas pire ou ya ke des a dans la chaine, tu va faire size(size+1)/2 = O(size²) itérations dans les 'for'. tu dois trouver un algo qui est en O(size), cad te débrouiller pour faire un algo sans 'for' imbriqué

cosmobob · Answer

bon j'ai trouvé une réponse en fait seulement 2 passages, mais ca utilise un tableau intérmédiaire.
char tab[size];
char tab2[size];
on remplit tab avec les a et les b.
pour tab2 : 
int valeur = 0;
for (i = 0; i < size; i++)
{
   if (tab[i] == 'b')
      valeur++;
   tab2[i] = valeur;
}
on constate qu'a la sortie, tab2[size-1] représente le nombre de 'b' dans la chaine; et que tab2[i] représente le nombre de 'b' jusqu'au i'eme caractere.
or maintenant pour chaque 'a', on peut savoir combien il y a de b qui suivent (donc de sous chaines qui commencent par ce 'a' la et qui finissent par un 'b') en calculant tab2[size-1]-tab2[i]

int nbsouschaine = 0;
for (i = 0; i > size; i++)
{
   if (tab[i] == 'a')
      nbsouchaine = nbsouschaine + tab2[size-1]-tab2[i];
}

ici on a le bon nbsouschaine :)
cet algo fait 2*size opérations, c'est a dire qu'il est en O(size), donc immensément plus rapide que le tiens !! (2n c'est bcp plus petit que n² quand n est grand). par contre, il a besoin d'une mémoire en O(size) (car on a besoin d'un tableau intermédiaire de taille size)

cs_jpeg · Answer

Pour accélére ton algo, utilise des pointeurs. Ce sera moins compréhensible mais bien plus rapide (surtout si size est élévé) 
Par exemple :

char tab[size];
char tab2[size];
char* ptab=tab;
char* ptab2=tab2;
char* pfintab2=&tab2[size-1];

int valeur = 0;
do
{
if (*ptab++ == 'b') valeur++;
*ptab2 = (char)valeur; // attention à la valeur (sur 1 octet)
}
while (ptab2++!=pfintab2);

int nbsouschaine = 0;
ptab=tab;
ptab2=tab2;

do
{
if (*ptab++ == 'a') nbsouchaine += (*pfintab2-*ptab2);
}
while (ptab2++!=pfintab2);

jpeg

MoDDiB · Answer

Ok meric desolé de pas avoir vu avant vos reponses mais la notification auto a dy foirer ^^
Merci encore jvé rebosser ca !!

MoDDiB · Answer

Ton algo semble bon cosmobob mais il ne passe que 3 tests sur 5 niveau calculs.. doit y avoir une erreur a partir d'un certain nombre v voir ca ^^

Algo trop lent :(

5 réponses

Votre réponse

Discussions similaires