如何计算函数的搜索复杂度

Question

我有以下两个函数，我正在尝试比较时间复杂度我的第一个函数是一个简单的 for 循环：

For (i=0;i<m;i++)
// do stuff

时间复杂度：

i=0 is executed once

i< n is executed n+1 times

i++ is executed n times

= 2n+2 = 0(N)

我正在努力计算第二个函数的时间复杂度：

void search(string word)
{
    Index index;
    if (tree.AVL_Retrieve(word, index)) {
        for (auto i : index.idList)
        {
            
             for (int j=0;j<m;j++)              
                 {
                    //do stuff
                  }
        }   
    }
}

我相信 AVL 树中的检索是 O(logN)，我的循环是 O(N)，然后我的内部循环是 O(M)，但作为一个整体，我将如何编写该搜索的时间复杂度功能。

注意：我们可以假设我的 AVL 树中有 N 个键

Answer 1

第一个for循环运行了(m-1)次，因此时间复杂度为O(m)。

第二个函数运行 AVL_Retrieve 函数一次，每个循环计数 index.idList 次，给出复杂度 O(log (number of nodes in tree))+O((count of index.idList)*m)

如何计算函数的搜索复杂度

how to work out the search complexity of a function

c++

big-o