java - 伪代码/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

Google永远不会停止惊奇，我会在 29 日到期吗？ ;)

Java 翻译是个好主意，一旦可操作，如果您在可视化算法时遇到问题，您将能够逐步查看它以准确了解算法的作用。

一些提示:伪代码的数组索引为 1 到 n，Java 的数组索引为 0 到 length - 1 。您的循环需要修改以适应这一点。此外，您还保留了循环中的增量 - i++、j++。

使 b 魔法常量大小也不是一个好主意 - 查看伪代码我们可以看到它最多被写入 n - 1 次，所以这将是一个很好的起点它的大小。您可以调整它的大小以适应最后。

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