伪代码/ Java神秘算法

Question

我有一个算法,我想知道它的作用.我相信你们中的一些人可以看看这个并告诉我它的作用,但我已经看了半个小时了,我仍然不确定.当我尝试玩它时,它会变得混乱.打破像这样的算法你有什么技巧？我如何分析这样的东西,知道发生了什么？

我的猜测是它将数字从最小到最大排序,但我不太确定.

1. mystery(a1 , a2 , . . . an : array of real numbers)
    2. k = 1
    3. bk = a1
    4. for i = 2 to n
        5. c = 0
        6. for j = 1 to i ? 1
            7. c = aj + c
        8. if (ai ? c)
            9. k = k + 1
           10. bk = ai
    11. return b1 , b2 , . . . , bk

这是我尝试用Java编写的等价物,但我不确定我是否正确翻译:

public int[] foo(int[] a) {
        int k=1;
        int nSize=10;
        int[] b=new int[nSize];
        b[k]=a[1];
        for (int i=2;i<a.length;){
            int c=0;
            for (int j=1;j<i-1;)
                c=a[j]+c;
            if (a[i]>=c){
                k=k+1;
                b[k]=a[i];

Answer 1

谷歌从未停止过惊艳,因为29日我会接受它吗？;)

Java翻译是一个好主意,一旦操作,您将能够逐步完成它,以便在您可视化时遇到问题时确切了解算法的作用.

几个要点:在伪代码中有索引的数组1通过n,Java的数组被索引0通过length - 1.您的循环需要修改以适应这种情况.你还离开了循环的增量 - i++, j++.

使b magic恒定大小也不是一个好主意 - 看看我们可以看到它在大多数n - 1时间写入的伪代码,所以这将是它的大小的一个很好的起点.你可以调整它的大小以适应最后.

最后提示,算法的O(n ²)定时.这很容易确定 - 外部循环运行n次,内部循环n/2次,总运行时间为(n*(n/2)).n*n占主导地位,这就是Big O所关注的,使其成为O(n ²)算法.