求两数相加问题两种Java实现的Big O时间复杂度计算方法

大O表示法描述的是算法的时间/空间消耗随输入规模增长的渐近趋势，计算规则如下：

• 只保留最高阶的增长项，忽略低阶项
• 去掉所有常数系数，常数时间操作统一记为O(1)
• 嵌套循环的复杂度是内外层复杂度的乘积，平行循环的复杂度是各循环复杂度的和

设链表l1的长度为m，链表l2的长度为n。

命令式实现（addTwoNumbersImplementation1） #

• 时间复杂度：O(max(m,n))
  计算过程：整个逻辑只有一个平行while循环，循环的终止条件是两个链表的元素都被取完，总共执行次数为两个链表中更长的那个的长度。循环内的pollLast取值、加法运算、结果插入、进位标记操作都是常数时间O(1)，循环结束后如果有进位仅多执行1次常数插入操作，忽略常数项后最终时间复杂度为O(max(m,n))。
• 空间复杂度：O(max(m,n))
  仅需要存储结果列表，结果的最大长度为max(m,n)+1，忽略常数项后和输入规模正相关。

Stream实现（addTwoNumbersImplementation2） #

• 时间复杂度：O(m + n)
  注意：该实现存在致命缺陷，Java的Integer类型最大值为2^31-1，仅能存储10位以内的正整数，只要输入链表长度超过10位就会触发数值溢出，无法正常运行。
  计算过程：该实现包含多轮平行遍历操作：
  1. 遍历l1转字符串拼接：O(m)
  2. 字符串反转、转Integer：O(m)
  3. 遍历l2执行同样的转换逻辑：O(n)
  4. 整数相加：O(1)
  5. 结果转字符串、反转、转结果列表：O(max(m,n))
     所有操作的最高阶项为m+n，因此渐近时间复杂度为O(m+n)，和实现1同阶，但多轮遍历、字符串转换、装箱拆箱带来的常数开销远高于实现1，实际运行速度慢很多。
• 空间复杂度：O(m + n)
  需要额外存储两个输入链表转换得到的字符串、中间整数、结果字符串，空间开销明显高于实现1。

不用找零散的文档，直接看经典教材的基础章节即可：

• 《算法导论》第一部分的第3章（函数的增长）、第4章（分治策略）系统讲解了大O表示法的计算逻辑和典型场景
• 国内计算机专业通用的《数据结构与算法》教材开篇的算法效率分析章节，内容更贴合国内面试的考察范围
  看完基础概念后，每写一段算法代码都主动计算时间、空间复杂度，和标准题解的结论对照，练几十道题就能熟练掌握。

package exercises;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;


/**
 * 给定两个非空链表，分别代表两个非负整数，数位按逆序存储，每个节点仅存储一位数字。
 * 请将两数相加，以链表形式返回对应的和。你可以假设两数除了0本身之外不存在前导零。
 */
public class AddTwoNumbers {

    // 两种实现中效率更高的版本
    private List<Integer> addTwoNumbersImplementation1(LinkedList<Integer> l1, LinkedList<Integer> l2) {

        Integer carry = 0;
        List<Integer> result = new ArrayList<Integer>();
        while (l1.size() > 0 || l2.size() > 0) {

            Integer l1Last = Optional.ofNullable(l1.pollLast()).orElse(0);
            Integer l2Last = Optional.ofNullable(l2.pollLast()).orElse(0);

            Integer partialResult = l1Last + l2Last + carry;

            if (partialResult >= 10) {
                result.add(Character.getNumericValue(partialResult.toString().charAt(1)));
                carry = 1;
            } else {
                result.add(partialResult);
                carry = 0;
            }
        }

        if(carry == 1) {result.add(1);}

        return result;
    }


    // 两种实现中效率更低的版本
    private List<Integer> addTwoNumbersImplementation2(LinkedList<Integer> l1, LinkedList<Integer> l2) {
        Integer n1 = Integer.parseInt(new StringBuffer(l1.stream().map(e -> e.toString()).collect(Collectors.joining())).reverse().toString());
        Integer n2 = Integer.parseInt(new StringBuffer(l2.stream().map(e -> e.toString()).collect(Collectors.joining())).reverse().toString());
        Integer result = n1 + n2;
        return new StringBuffer(result.toString()).reverse().toString().chars().mapToObj(Character::getNumericValue).collect(Collectors.toList());
    }


    @Test
    public void test() {
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.addAll(Arrays.asList(2,4,3));
        LinkedList<Integer> list2 = new LinkedList<>();
        list2.addAll(Arrays.asList(5,6,4));
        List<Integer> resultList = new LinkedList<>();
        resultList.addAll(Arrays.asList(7,0,8));
        Assert.assertEquals(resultList, addTwoNumbersImplementation1(list1, list2));
    }

    @Test
    public void test2() {
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.add(0);
        LinkedList<Integer> list2 = new LinkedList<>();
        list2.add(0);
        List<Integer> resultList = new LinkedList<>();
        resultList.add(0);
        Assert.assertEquals(resultList, addTwoNumbersImplementation1(list1, list2));
    }

    @Test
    public void test3() {
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.addAll(Arrays.asList(9,9,9,9,9,9,9));
        LinkedList<Integer> list2 = new LinkedList<>();
        list2.addAll(Arrays.asList(9,9,9,9));
        List<Integer> expected = new LinkedList<>();
        expected.addAll(Arrays.asList(8,9,9,9,0,0,0,1));
        Assert.assertEquals(expected, addTwoNumbersImplementation1(list1, list2));
    }


    @Test
    public void test4() {
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.addAll(Arrays.asList(2,4,3));
        LinkedList<Integer> list2 = new LinkedList<>();
        list2.addAll(Arrays.asList(5,6,4));
        List<Integer> resultList = new LinkedList<>();
        resultList.addAll(Arrays.asList(7,0,8));
        Assert.assertEquals(resultList, addTwoNumbersImplementation2(list1, list2));
    }

    @Test
    public void test5() {
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.add(0);
        LinkedList<Integer> list2 = new LinkedList<>();
        list2.add(0);
        List<Integer> resultList = new LinkedList<>();
        resultList.add(0);
        Assert.assertEquals(resultList, addTwoNumbersImplementation2(list1, list2));
    }

    @Test
    public void test6() {
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.addAll(Arrays.asList(9,9,9,9,9,9,9));
        LinkedList<Integer> list2 = new LinkedList<>();
        list2.addAll(Arrays.asList(9,9,9,9));
        List<Integer> expected = new LinkedList<>();
        expected.addAll(Arrays.asList(8,9,9,9,0,0,0,1));
        Assert.assertEquals(expected, addTwoNumbersImplementation2(list1, list2));
    }
}

内容的提问来源于stack exchange，提问作者fgonzalez