Re: Somme, récursive

From	Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid>
Newsgroups	fr.comp.lang.python
Subject	Re: Somme, récursive
Date	2021-04-30 12:07 +0200
Organization	Université de Strasbourg
Message-ID	<87a6pg84r6.fsf@universite-de-strasbourg.fr.invalid> (permalink)
References	<48-dnbOA4f2klhb9nZ2dnUU7983NnZ2d@giganews.com> <87mttgakrp.fsf@izac.org> <s6g30m$1j1n$1@gioia.aioe.org>

Show all headers | View raw

Dominique <zzz@aol.com.invalid> writes:

> Le 29/04/2021 à 22:38, Benoit Izac a écrit :
>
>> La valeur maximale d'une liste c'est la plus grande valeur entre le
>> premier élément et la valeur maximale des éléments suivants.
>
> Bonjour,
>
> Je comprends mal quelle peut-être cette plus grande valeur que tu évoques.
>
> Si liste=[4,7,5,5,2,6,9,3,8,4], je serais tenté d'isoler liste[0] avec
> deb=liste[0], le retirer de liste, puis de faire
> liste.sort(revere=)True) et prendre liste[0] et faire deb+liste[0]
>
> Mais c'est si simple que ça ne doit pas être ça

Ce n'est pas un problème de simplicité, c'est un problème de complexité
(au passage, il est inutile d'enlever le premier élément, tu peux trier
et prendre le premier/dernier selon que tu veux le min/max -- ou
l'inverse avec reverse ; en fait je ne comprends pas ton idée avec le
premier élément).

Le problème de complexité est : trier une liste de n élements coûte
environ n*log(n) comparaisons, alors que trouver le min/max ne devrait
coûter que environ n opérations (comparer un nouvel élément avec le
min/max déjà connu des éléments déjà consultés).

Ce qu'explique Benoît, c'est comment déterminer le min/max sans utiliser
une opération qui coûte plus cher que cette recherche, en utilisant
uniquement les opérations de base sur les listes. C'est un algorithme,
qui doit être récursif (pour ce qu'on comprend de la question initiale).

(En Python, il y a aussi les fonctions min()/max(), mais manifestement
ici il faut l'écrire soi-même.)

Enfin, je ne vois pas pourquoi trouver le min/max d'une liste devrait
détruire la liste à grands coups de del...

-- Alain.

Back to fr.comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Somme, récursive raph14 <nospam_rgb.baralle@gmail.com.invalid> - 2021-04-29 14:38 -0500
  Re: Somme, récursive Benoit Izac <use.reply.to@INVALID.ADDRESS> - 2021-04-29 22:38 +0200
    Re: Somme, récursive Dominique <zzz@aol.com.invalid> - 2021-04-30 07:02 +0200
      Re: Somme, récursive Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2021-04-30 12:07 +0200
    Re: Somme, récursive raph14 <nospam_rgb.baralle@gmail.com.invalid> - 2021-04-30 09:56 -0500
    Re: Somme, récursive raph14 <nospam_rgb.baralle@gmail.com.invalid> - 2021-04-30 09:57 -0500
    Re: Somme, récursive Olivier Miakinen <om+news@miakinen.net> - 2021-04-30 17:06 +0200
      Re: Somme, récursive Olivier Miakinen <om+news@miakinen.net> - 2021-04-30 17:17 +0200
        Re: Somme, récursive Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2021-04-30 18:14 +0200
          Re: Somme, récursive raph14 <nospam_rgb.baralle@gmail.com.invalid> - 2021-04-30 11:46 -0500
        Re: Somme, récursive Benoit Izac <use.reply.to@INVALID.ADDRESS> - 2021-04-30 20:09 +0200
          Re: Somme, récursive raph14 <nospam_rgb.baralle@gmail.com.invalid> - 2021-04-30 14:04 -0500
            Re: Somme, récursive Benoit Izac <use.reply.to@INVALID.ADDRESS> - 2021-04-30 21:15 +0200
  Re: Somme, récursive debimax <debimax@free.fr> - 2021-04-30 15:03 +0200
    Re: Somme, récursive Dominique <zzz@aol.com.invalid> - 2021-04-30 18:46 +0200
      Re: Somme, récursive debimax <debimax@free.fr> - 2021-04-30 22:05 +0200
        Re: Somme, récursive Dominique <zzz@aol.com.invalid> - 2021-05-01 04:39 +0200

csiph-web