Comment fonctionne la méthode .min et .max de ruby, et quelle est la complexité du temps lors de l'utilisation de ces méthodes pour trouver la valeur min ou max dans un tableau?

Contexte:Comment fonctionne la méthode .min et .max de ruby, et quelle est la complexité du temps lors de l'utilisation de ces méthodes pour trouver la valeur min ou max dans un tableau?

Je cherchais un problème d'algorithmes pour déterminer max_stock_profit quand on me donnait un tableau des prix des actions. J'essayais de déterminer la complexité temporelle de cette méthode, et j'ai rencontré un .min utilisé sur un tableau dans la méthode each. Cela m'a conduit à poser la question intitulée dans ce post.

De façon générale, quand on regarde simplement à la méthode .min ou .max sur un tableau de longueur 1.000.000 par exemple, ne serait pas en cours d'exécution ou .min.max sur la matrice linéaire besoin de temps en O (n) pour déterminer une valeur minimum ou maximum, où n est la longueur du tableau? ..

Si oui, en fonction du code d'exemple ci-dessous, en exécutant .min ou .max méthode dans une méthode each, ne serait pas la complexité du temps O (n^2) puisqu'il doit exécuter une autre itération dans la méthode each pour déterminer la valeur min? Je pense que l'extrait de code devrait fonctionner à l'heure O (n), mais mon manque de compréhension de la façon dont fonctionne .min et .max est ce qui cause une grande confusion. Est-ce parce que .min est invoqué sur un tableau contenant seulement 2 valeurs, il est normal que cette ligne de code fonctionne en temps constant O (1)? Toute aide pour effacer mon incompréhension de ce qui se passe serait appréciée. Merci.

Exemple extrait de code:

stock_prices = [5, 7, 2 ,4, 9, 1, 8] 
min_price = stock_prices[0] 
max_profit = 0 

stock_prices.each do |current_price| 
    min_price = [min_price, current_price].min 
    potential_profit = current_price - min_price 
    max_profit = [max_profit, potential_profit].max 
end

Source

2017-10-11 George.

Que fait-on avec le 'etc ...'? Cela peut être pertinent pour la raison pour laquelle la personne qui a écrit ceci n'a pas simplement dit 'min_price = stock_prices.min'. Par exemple, c'est peut-être un processus séquentiel et la logique est fondée sur le cours de bourse le plus bas observé jusqu'ici. – pjs

oui c'est un processus séquentiel et est basé sur le prix de l'action le plus bas en comparant le prix min initial et le prix actuel. Mais je suis confus quant à la complexité temporelle de cet extrait de code, en particulier lors de l'implémentation de .min et .max dans la méthode .each. Je pensais en utilisant .min, il nécessite une autre itération dans .each, ce qui me conduit à croire que la complexité du temps prend plus de temps que O (n)? –

Je crois que le code est ici O (n), c'est linéaire sur la base de la longueur des cours des actions – stujo

Les opérations .min et .max dans le each sont appliquées aux matrices avec seulement deux éléments, de sorte que chacun est une opération O (1). Changer n, le nombre d'éléments dans stock_prices, ne changera pas le temps de trouver le .min ou .max dans chaque itération, ils sont indépendants de n. Par conséquent, le bloc entier est O (n).

Source

2017-10-11 21:34:32 pjs

Ok, merci pour la réponse. D'une manière générale, si la matrice était plus grande, disons de longueur 1000, la méthode min/max prendrait un temps linéaire puisqu'elle a parcouru chaque élément correct? Je demande parce que je dois être plus prudent en utilisant libéralement .min ou max dans un autre itérateur si je voulais optimiser l'exécution –

'min' est linéaire dans la taille du tableau * il est itératif sur *. MAIS! Dans ce cas, la taille du tableau dont 'min' est l'itération est limitée par une constante (2 dans l'exemple original, 1000 dans votre hypothétique). * Chaque fois qu'une fonction est bornée par une constante, elle est dans O (1). (Il suffit de le brancher dans la définition de Big-Oh et vous verrez.) Bottom line: toujours faire attention à définir rigoureusement ce que "n" est, en parlant de la complexité du temps en fonction de n. –

@GeorgeV. Non, car il ne parcourt pas le tableau d'origine. Le bloc 'each' crée des tableaux temporaires contenant seulement 2 éléments, donc la quantité de travail par itération n'a rien à voir avec la longueur du tableau d'origine. – pjs

Comment fonctionne la méthode .min et .max de ruby, et quelle est la complexité du temps lors de l'utilisation de ces méthodes pour trouver la valeur min ou max dans un tableau?

Répondre

Questions connexes