问线性时间内阵列的每个元素与每个元素的绝对差
EN

Stack Overflow用户

提问于 2017-06-03 04:26:40

回答 1查看 25关注 0票数 0

给定一个数组

a[4]={2,5,8,9};

每个元素的绝对差异是

(3,6,7,3,4,1)
abs(2-5)=3
abs(2-8)=6
abs(2-9)=7
abs(5-8)=3
abs(5-9)=4
abs(8-9)=1

有没有可能在线性时间内找到它？如果是，是如何实现的？

发布于 2017-06-03 04:34:32

如果n是元素的数量，你必须做(n-1) + (n-2) + ... +1个比较，显然你可以这样做，所以它看起来像θ(n^2)个比较。如果你能在线性时间内做到这一点，那么冒泡排序就是线性的(它是n^2)。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/44336944

复制

相似问题

问线性时间内阵列的每个元素与每个元素的绝对差EN