使用嵌套的 If statements/method 调用分析 Big-Oh 表示法

Question

我在完全掌握 Big-Oh 表示法时遇到了一些麻烦，虽然我看到了 If 语句的一些答案，但我没有看到 if/else 语句中的任何方法调用。我在下面发布相关代码，线性和二进制搜索是标准实现（我本可以使用数组 class 但选择自己练习编码）。精确和一般的 Big Oh 符号都会有所帮助。我在下面做了尝试。

public static int count(int[][] myArray, int query) 
{
    queryHits = 0;   -----> O(1)
    queryNumber++;   -----> O(1)
    int subArraymin; -----> O(1)
    int subArraymax;  ----> O(1)
    int foundIndex = -1; -> O(1)
    int j = 5000;    -----> O(1)


        for (int i = 0; i<5000; i++)        ------------>O(5000 * O(?)
        { 
            subArraymin = myArray[0][j];        -------> O(1)
            subArraymax = myArray[999][j];       ------> O(1)

            if (query >= subArraymin && query <= subArraymax)     ----> O(1?)
            {
                foundIndex = binarySearch(myArray,0 , 1000, query, j); -->O(5000?) * O(log n)

                if (foundIndex == -1)       --> O(1?)
                {
                //irrelevant code omitted 
                }
                else 
                {
                    linearSearch(myArray, query, foundIndex, j);    -----> O(5000?) * O(n)
                }
            }
            else //irrelevant code omitted
        }
        return queryHits;
        }

我的主要问题：
1. 我的 if 语句是 O(1) 还是 O(n)？ 2. 我相信我的 for 循环是 O(5000 * 循环体) 但由于我调用了两种不同的方法，那些方法的大哦首先得到乘法吗？

感谢您的任何 help/pointers！

Answer 1

画出代码流程图，尤其是if分支和循环。这很有帮助。或者，在您的代码上绘制适当的流程线。

在这种情况下，函数的复杂性得到增加，而不是增加，因为它们以线性顺序出现。正如您在“5000*”中所指出的那样，循环就是乘法。

因此，循环的复杂度为 5000*(O(log n) + O(n))。这简化为 O(n)，因为 5000、1000 和其他杂项都是标量常数。如果“5000”来自其他一些输入参数（您可能称之为 "m"），则算法为 O(m*n).

到目前为止，您觉得其中有多少意义？

使用嵌套的 If statements/method 调用分析 Big-Oh 表示法

Analyzing Big-Oh Notation with nested If statements/method calls

java

methods

performance

big-o

if-statement