我正在練習一些編碼演算法。在某些面試中，他們不僅要求您解決問題，而且要求您以最有效的方式解決問題，并指定演算法的效率（又名 Big 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));
}
}
uj5u.com熱心網友回復：
對于回圈，大 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（或 40 億）的數字。第一個會。忽略這一點，做映射是一個 O(n) 操作，然后是一個 O(n) 操作來連接它們，然后是一個 O(n) 操作來反轉它。所以它是 O(3n)，與 O(n) 相同。
這意味著復雜性明智，它們是相同的。Timewise - 第一個演算法會讓第二個演算法大吃一驚，因為您執行 n 次的操作效率更高，特別是如果您擺脫了不必要的字串使用并使用我向您展示的代碼。為了比較，復雜性是時間的近似值，但不是直接相關。它只能用于比較不同類別的演算法（比如 O(n) 與 O(n^2)），并且僅在大 n 時有效。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/310825.html
上一篇：已驗證的現有列上的SQLite資料庫“無此類列”錯誤
下一篇：requireActivity().getApplicationContext()“可能會產生一個NullPointerExeption”