时间复杂度（勾股三元组）

Question

我写了两种不同的算法来计算勾股三元组：

import java.util.*;

class Untitled {
  public static void main(String[] args) {

    int n = 20;

    System.out.println("--------------------");
    algorithmOne(n);
    System.out.println("--------------------\n");
    algorithmTwo(n);
    System.out.println("--------------------");
  }

  public static void algorithmOne(int n){

    long startTime = System.nanoTime();

    for (int i = 1 ; i <= n ; i++) {
      for (int j = 1 ; j <= n ; j++) {
        for (int k = 1; k <= n ; k++) { 
          if (Math.pow(i,2) + Math.pow(j,2) == Math.pow(k,2)) {
            System.out.println(i + "," + j + "," + k);
          }
        }
      }
    }

    System.out.println("Run Time: " + (System.nanoTime() - startTime)/1000000 + " milliseconds");
  }

  public static void algorithmTwo(int n){

    long startTime = System.nanoTime();

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

    // O(n)
    for(int i = 1 ; ; i++) {
      if ((int)Math.sqrt(i) > n) {
        break;
      }
      if (Math.sqrt(i) == (int)Math.sqrt(i)) {
        squares.add(i);
      }
    }

    // O(n^3)
    for (int i = 0 ; i < squares.size() ; i++) {
      for (int j = 0 ; j < squares.size() ; j++) {
        for (int k = 0 ; k < squares.size() ; k++) {
          if (squares.get(i) + squares.get(j) == squares.get(k)) {
            System.out.println((int)Math.sqrt(squares.get(i)) + "," + (int)Math.sqrt(squares.get(j)) + "," + (int)Math.sqrt(squares.get(k)));
          }
        }
      }
    }

    System.out.println("Run Time: " + (System.nanoTime() - startTime)/1000000 + " milliseconds");

  }
}

我相信两种算法都为O（n ^ 3），但是当我计算它们运行的​​时间时，第二种算法要快得多。使用n = 20，algorithm1大约需要60毫秒，而算法大约需要5毫秒。这两种算法如何具有相同的时间复杂度，但是一种算法比另一种算法运行得更快？我知道第二个算法不必在三重for循环中迭代尽可能多的数字，但是这不意味着时间复杂度会降低吗？

Answer 1

您必须先了解复杂性。

让我们举个例子。

假设您有一个可以容纳5公斤苹果的袋子，但是不管有多少苹果。它的重量为5公斤，但可以是20个苹果，也可以是5个苹果。

因此，当我们谈论时间复杂性时，您谈论的是数量（以千克为单位）而不是苹果的数量（它可能是内存复杂性）。

这意味着当您谈论big-Oh时，您必须知道它的意思。O（n ³）表示最多需要该数量。因此，它可以计算每个步骤，但最多n ³，或者可以跳过某些步骤，但最多需要n ³。我想，您现在很清楚为什么我要使用at most。

您的第二个算法正在跳过某些步骤，但没有。因此，第二个算法的运行速度要快一点，但是从大哦的意义上讲，它可能需要at most这个量（O（n ³）），并且列表的大小仍然很重要。

其他信息：

That is called Pythagorean triple. O(|result|) solution exists. 
You can look it up on Wikipedia.
Also learn Stern-Brocot tree that is the essential part to write the most optimal case.
To learn the theory, search rational points on circle. 
Not an easy topic but helps if you know a little geometry.

Answer 2

big-O表示法“隐藏常数”。两种算法，一种以5n^3毫秒运行，另一种以5000000n^3毫秒运行，两者都具有复杂度O(n^3)，但是第二种算法则要慢一百万倍。这就是为什么big-O符号不能说明整个故事的原因。例如，O(N log N)有很多不同的排序算法，但是其中一些算法比其他算法更快，或者在特定输入上比其他算法更快，等等。。。性能要比基本的算法入门书告诉你的更多。

就您的代码而言，似乎访问数组中的值比计算Math.pow更快，因此，预先计算平方的版本总体上更快。但是，我想Java中的Math.pow比简单的整数乘法要贵。我尝试将其替换为简单的平方：i*i + j*j == k*k，然后查看是否有任何显着差异。

---

我在您的代码中注意到的另一个不相关的事情是，您假设平方计算循环的复杂度为O(n)：

// O(n)
for(int i = 1 ; ; i++) {
  if ((int)Math.sqrt(i) > n) break;
  ...
}

但这不是事实。您在sqrt(i) <= n时循环，即i <= n*n。因此，该循环执行了n^2次，因此该循环的复杂度为O(n^2)。以下循环确实具有O(n)复杂度：

// O(n)
for(int i = 1 ; i<=n; i++) {
   squares.add(i*i);
}

它将运行得更快，但是由于整个算法的整体O(n^3)复杂性，不会有太大的不同。