Java : Testing Array Sum Algorithm Efficiency

Question

我在大学学习 Java 类(class)，我的笔记提供了 3 种计算 ArrayList 总和的方法。一是迭代，二是递归，三是数组拆分结合递归。

我的问题是如何测试这些算法的效率？实际上，我认为算法计算值所需的步骤数可以告诉您算法的效率。

我的 3 种算法代码:

import java.util.ArrayList;
public class ArraySumTester {

    static int steps = 1;

    public static void main(String[] args) {

        ArrayList<Integer> numList = new ArrayList<Integer>();

        numList.add(1);
        numList.add(2);
        numList.add(3);
        numList.add(4);
        numList.add(5);


        System.out.println("------------------------------------------");
        System.out.println("Recursive array sum = " + ArraySum(numList));

        System.out.println("------------------------------------------");
        steps = 1;
        System.out.println("Iterative array sum = " + iterativeSum(numList));

        System.out.println("------------------------------------------");
        steps = 1;
        System.out.println("Array sum using recursive array split : " + sumArraySplit(numList));

    }

    static int ArraySum(ArrayList<Integer> list) {
        return sumHelper(list, 0);
    }

    static int sumHelper(ArrayList<Integer> list, int start) {
        // System.out.println("Start : " + start);
        System.out.println("Rescursive step : " + steps++);
        if (start >= list.size())
            return 0;
        else
            return list.get(start) + sumHelper(list, start + 1);

    }

    static int iterativeSum(ArrayList<Integer> list) {
        int sum = 0;
        for (Integer item : list) {
            System.out.println("Iterative step : " + steps++);
            sum += item;
        }
        return sum;
    }

    static int sumArraySplit(ArrayList<Integer> list) {

        int start = 0;
        int end = list.size();
        int mid = (start + end) / 2;

        System.out.println("Rescursive step : " + steps++);
        //System.out.println("Start : " + start + ", End : " + end + ", Mid : " + mid);
        //System.out.println(list);

        if (list.size() <= 1)
            return list.get(0);
        else
            return sumArraySplit(new ArrayList<Integer>(list.subList(0, mid)))
                    + sumArraySplit(new ArrayList<Integer>(list.subList(mid,
                            end)));

    }
}

输出:

------------------------------------------
Rescursive step : 1
Rescursive step : 2
Rescursive step : 3
Rescursive step : 4
Rescursive step : 5
Rescursive step : 6
Recursive array sum = 15
------------------------------------------
Iterative step : 1
Iterative step : 2
Iterative step : 3
Iterative step : 4
Iterative step : 5
Iterative array sum = 15
------------------------------------------
Rescursive step : 1
Rescursive step : 2
Rescursive step : 3
Rescursive step : 4
Rescursive step : 5
Rescursive step : 6
Rescursive step : 7
Rescursive step : 8
Rescursive step : 9
Array sum using recursive array split : 15

现在，从上面的输出来看，递归数组拆分算法的步数最多，但根据我的笔记，它与迭代算法一样高效。那么我的代码或我的笔记哪个不正确？

Answer 1

你只是想看看执行速度吗？如果是这样，您将需要查看微基准测试: How do I write a correct micro-benchmark in Java?

本质上，由于 JVM 和现代处理器的工作方式，您无法通过在 FOR 循环中运行一百万次并使用系统计时器 (EDIT) 测量执行速度来获得一致的结果。

也就是说，“效率”还可以指其他方面，例如内存消耗。例如，任何递归方法都有堆栈溢出的风险，这个站点就是以这个问题命名的:)尝试给 ArrayList 数万个元素，看看会发生什么。