有没有办法只用一次迭代来标准化一组值？

Question

所以说我有一个大的浮动列表,我想将它们全部归一化为min和之间的值max.例如,{2, 5, 10}与min = 0和max = 2一组的结果{0.4, 1, 2}.

我目前的算法是

1. 遍历所有元素并找到集合的总和
2. 再次遍历所有元素,除以总和(占最小值和最大值)

我的问题是一般的算法 - 是否可以O(n)代替进行此操作O(2n)？

Answer 1

首先,O(n)=O(2n)它是一个渐近分析.回到你的问题,你可以这样做:

1. 迭代所有元素并找到集合的最小值/最大值
2. 使用延迟评估技术:不要再次遍历所有元素.当您要求i从集合中输入对象时,将其返回到您在1中计算的标准化函数.

请注意,您无法避免集合中每个元素的2次读取.