Quelle est la complexité de ce genre spécialisé

Question

Je voudrais connaître la complexité (comme dans O (...)) de l'algorithme de tri suivant:

• Il y a de barils B
• qui contiennent un total de N éléments, répartis inégalement à travers les barils.
• Les éléments de chaque canon sont déjà triés.

Le genre combine tous les éléments de chaque cylindre en une seule liste triée:

• en utilisant un tableau de taille B pour stocker le dernier élément de classement de chaque cylindre (à partir de 0)
• vérifier chaque baril (au dernier indice stocké) et trouver le plus petit élément
• copie l'élément dans le tableau trié final incrémenter le compteur de tableau
• incrément le dernier élément pour le canon Sorted nous avons choisi de
• effectuer ces étapes N fois

ou dans le code pseudo:

for i from 0 to N 
    smallest = MAX_ELEMENT 
    foreach b in B 
     if bIndex[b] < b.length && b[bIndex[b]] < smallest 
      smallest_barrel = b 
      smallest = b[bIndex[b]] 
    result[i] = smallest 
    bIndex[smallest_barrel] += 1 

Je pensais que la complexité serait O (n), mais le problème que j'ai à trouver la complexité est que si B grandit, il a un impact plus grand que si N grandit parce qu'il ajoute un autre tour dans la boucle B. Mais peut-être que cela n'a aucun effet sur la complexité?

Answer 1

Puisque vous avez déjà du pseudo-code, trouver la complexité est facile. Vous avez 2 boucles imbriquées. L'externe court toujours N-1 fois, l'interne toujours | B |, où | B | est la taille de l'ensemble B (nombre de barils). Donc la complexité est (N-1) * | B | qui est O (NB).

Answer 2

Vous avez raison de dire que le nombre de barils modifie la complexité. Regardez simplement votre pseudo-code. Pour chaque élément que vous êtes sur le point de choisir, vous devez rechercher le tableau des candidats, dont la longueur est B. Donc vous effectuez une opération de complexité O (B) N fois