文章/答案/技术大牛

发布

社区首页 >问答首页 >在降低大O复杂度方面找到一种有效的算法

问在降低大O复杂度方面找到一种有效的算法
EN

Stack Overflow用户

提问于 2013-10-20 05:01:49

回答 2查看 677关注 0票数 0

给定一个由N个元素组成的有序数组。需要找出所有元素的差的绝对和。例如:给定4个元素1、2、3和4。|1-2|+|1-3|+|1-4|+|2-3|+|2-4|+|3-4| = 10。下面是我的java代码：

List<Integer> a = new ArrayList<Integer>(); //just for understanding , the Array List is already filled with numbers 
public static int lsum(int N)//consider the arraylist to be sorted in ascending order.
{
    int sum =0;

    for( int i=0;i<N;i++)
    {
        int w =a.get(i);
        for(int j =i;j<N;j++)
        {
            int z = a.get(j);
            sum =sum +(z-w);
        }

        }
    return(sum);

}

寻找有效的算法，而不是我使用的简单算法{ O(n^2)复杂度}。这是需要此功能的更大程序的要求。输入(元素的数量)可以大到10^5。

java

algorithm

nested-loops

回答 2

Stack Overflow用户

发布于 2013-10-20 07:11:23

如果您首先对元素进行排序，则可以将运行时设置为O(n log n)。

这里的思想是，如果a[]是按排序顺序排列的整数列表，b[i]是a[i]和其他数字之间的差之和，那么b[i+1]可以直接根据b[i]、i、a[i+1] - a[i]和数组的长度进行计算。

我不会说具体是怎么做的，但这里有一个提示。Math.abs(a[i+1] - a[j])和Math.abs(a[i] - a[j])能有多大的不同？对于哪个j，Math.abs(a[i+1] - a[j])更强大？对于哪个j，它更小？

现在，在你计算了这些之后，它们之间的b[i]包含了两次每个差。你想要的值就是它们的和除以2。

票数 1

Stack Overflow用户

发布于 2013-10-20 07:42:33

如果数组为x_1 <= x_2 <= .. <= x_n

涉及x_r的项的总和是U_r + (2r -n) x_r - L_r

U_r = x_{r+1} + x_{r+2} + ... + x_n和L_r = x_1 + x_2 + ... + x_{r-1}在哪里

现在，您可以在一次遍历数组的过程中计算出O(n)时间内的所有U_i。L_i可以用U_i和元素的总和来编写。

因此，整个和可以在O(n)时间内计算。

一些玩弄数学的人应该会给你一个单次通过算法。

(我把细节留给你)。

票数 0

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

原文链接：

https://stackoverflow.com/questions/19471107

复制

相似问题

问在降低大O复杂度方面找到一种有效的算法
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在降低大O复杂度方面找到一种有效的算法EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在降低大O复杂度方面找到一种有效的算法
EN