我怎样才能计算这样一个程序的复杂性

Question

所以我一直在研究算法的复杂性，但是这个我看不懂。如果我使用一个全局变量来检查函数被调用了多少次，它将计算数字 11 然后说复杂度是 O(2*N)，但是在看问题时我认为复杂度是 O(N) .

#include <cstdlib>
#include <iostream>
  
using namespace std;
  
class node { 
    public:
    int data; 
    node* left; 
    node* right; 
      
    node(int data){
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
}; 

int funcUtil(node* node, int min, int max) { 
    cout << "a";
    if (node==NULL)
        return 1; 
    
    if (node->data < min || node->data > max)
        return 0; 
    
    return funcUtil(node->left, min, node->data-1) && funcUtil(node->right, node->data+1, max);
} 

int func(node* node) { 
    return(funcUtil(node, INT_MIN, INT_MAX)); 
} 
  
int main() { 
    node *root = new node(4); 
    root->left = new node(2);  
    root->right = new node(5); 
    root->left->left = new node(1); 
    root->left->right = new node(3); 
      
    if(func(root)) 
        cout<<"YES"; 
    else
        cout<<"NO"; 
          
    return 0; 
}

Answer 1

复杂度为O(2*N)，与O(N)相同，常量省略

Answer 2

大 O 表示法是这样工作的：

O(c * f(x)) = O(f(x)), c!=0

换句话说，您始终可以将括号内的函数乘以任意非零实常数。

所以 O(2N) = O(N)

大 O 表示法的另一个属性是您可以省略低阶项：

O(x^2 + x) = O(x^2)

O(a^x + p(x)) = O(a^x) where a>1 and p(x) is a polynomial of x

进一步阅读：https://en.wikipedia.org/wiki/Big_O_notation

Answer 3

从根本上说，如果你看一下 big-O 的含义，它意味着函数 f 的增长率比函数 g(n) 慢，所以我们写成 f(n) = O(g(n)) .

现在将其视为 n 和 2n 将始终具有相同的增长率，因为它们随着 n 的变化而变化，因此我们得出 O(n) 与 O(2n) 相同的结论，并且现在我们将使用 O(n)，因为它是描述线性增长率的标准形式。

我怎样才能计算这样一个程序的复杂性

How can I calculate the complexity of a program like this

c++

algorithm

complexity-theory

time-complexity

code-complexity