sur Select algorithme

Question

J'ai lu sur le selection algorithm et j'ai une question peut-être il semble stupide !!! mais pourquoi considérons-nous le tableau comme des groupes de 5 éléments ?? Pouvons-nous le considérer avec 7 ou 3 éléments? Merci aussi y at-il un lien pour m'aider à mieux comprendre ce but?

aussi c'est ma preuve quand on considère le tableau avec 3 éléments et c'est toujours l'ordre de n, pourquoi? Est-ce correct?

T(n)<=T(n/3)+T(n/3)+theta(n) 
claim: T(n)<=cn 
proof: For all k<=n : T(n)<=ck 
    T(n)<=(nc/3)+(nc/3)+theta(n) 
    T(n)<= (2nc/3)+theta(n) 
    T(n)<=cn-(cn/3-theta(n)) and for c>=3 theta(n) this algorithm with this condition will have an order of n,too !!!! 

Answer 1

Je pense que vous avez fait une erreur pour T (n). Il devrait être T (n) = T (n/3) + T (2n/3) + O (n).

Le T (n/3) sert à trouver le pivot (médiane des médianes). Seulement la moitié de tous les groupes n/3 ont une médiane plus petite que le pivot. Ces groupes ont 2 éléments plus petits que le pivot. Donner 2 * (1/2 * n/3) == n/3 éléments plus petit que le pivot. Ainsi, seulement 33% doit être plus petit que le pivot (et 33% doit être supérieur au pivot). Donc, dans le pire des cas, vous avez encore 66% pour l'itération suivante, T (2n/3).

Je ne peux pas bien lire votre épreuve, mais maintenant il est impossible de le prouver. Droite?

Answer 2

Un peu de googling et j'ai trouvé this. Il y a une très petite section sur pourquoi 5, mais elle ne répond pas vraiment à votre question autrement que de dire que c'est le plus petit nombre impair possible qui peut être utilisé (doit être impair pour donner une médiane). Il y a une preuve mathématique que ça ne peut pas être 3 (mais je ne le comprends pas vraiment moi-même). Je pense que c'est essentiellement dire qu'il peut y avoir un nombre impair, 5 ou plus, mais le plus petit sera le mieux, je suppose, car il sera plus rapide de trouver la médiane dans le groupe plus petit?