如何找到这个函数的大O

Question

所以我有这个函数可以遍历 Java 中的 8x8 多维数组。我试图在 findTheBoss() 中理解这个函数的大 O。它在静态 8x8 网格中搜索给定字符串。我真的很想了解如何找到像这样的基本功能的大 O。我认为这是 O(n^2) 但我不确定。请帮助我了解如何找到此函数的方程式。

public static void FindTheBoss(String[][] bossGrid, String bossName){

    for(int i=0; i < bossGrid.length; i++)
    {               
        //Iterate through each row?

        for(int j=0; j < bossGrid[i].length; j++)
        {

            if(bossGrid[i][j].equals(bossName))
            {

                System.out.println("Found '" + bossName + "' at position "+ i + "," + j);
                break;
            }
        }

    }   

}

Answer 1

你几乎是对的。但是要小心，大 O 表示法可能会很棘手，即使当你有条理时它并不那么复杂。

让我们总结一下您的代码的作用：您收到一个大小为 NxN 的二维数组和一个长度为 S 的字符串，并尝试在矩阵中找到该字符串（一次或多次）。即使您 break 循环有时，也只是假设它不会发生那么多。然后，您只需遍历该矩阵的元素并比较每个元素的两个字符串。

基本上，如果你说这个算法是O(N^2)，它可能足够公平。但要小心知道 N 是什么。如果你的网格可以有 N 行和 M 列，你会说算法是 O(N*M)，也就是 O(N^2) 只有在正方形的情况下（这是一个很常见的错误）。

不过，我不会说这个算法是O(N^2)，而是O(S*N^2)。确实，equals 是做什么的？一个字符一个字符地比较，直到一个字符不同为止。在 N 很小但字符串非常长的情况下，您会发现考虑到这一点很重要。

注意：您可以阅读此 interesting thread 关于 String.equals() 的复杂性。如果比较预先计算的长度或哈希码，它显然可以比 O(S) 更快，但这些是内部优化，最坏的情况仍然是 O(S)。

Answer 2

这个post对一维数组的解释还是不错的。 https://justin.abrah.ms/computer-science/how-to-calculate-big-o.html

在这个 post 中，他谈到了二维数组： https://justin.abrah.ms/computer-science/big-o-notation-explained.html 他对二维数组的big-O的解释中有一个coursera link。

如何找到这个函数的大O

How to find big O of this function

java

big-o

loops

concept