最有效的算法和大 O 符号

Question

我正在练习一些编码算法。在一些面试中，他们不仅要求您解决问题，而且要求您以最有效的方式解决问题，并指定算法的效率（又名大 O 表示法）。我一直在衡量效率方面遇到问题，所以我非常感谢有人解释如何计算算法的效率或指向一些资源以检查它（到目前为止没有找到非常有用的文档）。

例如，看看下面这个问题。我用两种不同的方式解决了它。使用 Java。第一种方法是使用命令式方法（我发现它更有效，因为我们不需要多次迭代列表）和第二种方法，使用函数式编程方法和流 API（我发现很多在这种情况下效率较低）。

有人可以解释一下这两种方法的大 O 表示法是什么，并解释一下计算方法吗？

    package exercises;

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

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


/**
 * You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
 *
 * You may assume the two numbers do not contain any leading zero, except the number 0 itself.
 */
public class AddTwoNumbers {

    //Most efficient implemention of the two
    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;
    }


    //Least efficient implemention of the two
    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));
    }
}

Answer 1

对于循环，大O符号时间基本上是计算迭代次数。如果你遍历一个数组，它是 O(n)（n 是列表的大小）。如果循环内有循环，则其 O(外循环计数 * 内循环计数)。所以第一个算法是 O(n)，其中 n 是数组的大小。

另外-你在做什么

result.add(Character.getNumericValue(partialResult.toString().charAt(1)));
carry = 1;

这里有一个更简单的方法：

   result.add(partialResult%10);
   carry = partialResult/10;

如果您要添加 3 个或更多数组，这种方式也适用于完全相同的代码。

你的第二个有一个重大缺陷 - 它不适用于加起来超过 2^32（或 4 十亿）的数字。第一个会。忽略这一点，做映射是一个 O(n) 操作，然后是一个 O(n) 操作来连接它们，然后是一个 O(n) 操作来反转它。所以是O(3n)，和O(n)一样。

这意味着复杂性方面，它们是相同的。 Timewise——第一个算法将击败第二个算法，因为你执行 n 次的操作效率更高，特别是如果你摆脱不必要的字符串使用并使用我向你展示的代码。为了比较起见，复杂度是时间的近似值，但它不是直接相关的。它只能用于比较具有不同类的算法（例如 O(n) 与 O(n^2)）并且仅在大 n 时有效。

最有效的算法和大 O 符号

Most efficient algorithm and BigO notation

java

algorithm

java-stream

big-o

coding-efficiency