时间戳

首页 > 解决方案 > 递归的时间复杂度

time-complexity - 递归的时间复杂度

问题描述

下面是一个在三角形中找到最大和的算法。我想说这个算法是 O(N^2)，因为 findMax 函数调用可以替换为嵌套的 for 循环，遍历每个节点的每个子节点。然而，递归让我不确定。那么如何通过递归来判断这段代码的时间复杂度呢？

int maxValue = 0;

void findMax ( Node * n , int sum ) {

if ( n == NULL ) {

    if ( maxValue < sum ) {

        maxValue = sum ;

    }

    return ;

}

findMax (n - > leftChild , sum + n - > value ) ;

findMax (n - > rightChild , sum + n - > value ) ;
}

标签： time-complexity

解决方案

int maxValue = 0; // will be executed once so O(1).

void findMax ( Node * n , int sum ) {

if ( n == NULL ) { // Will be executed in every call of function so if considering the function is called C times it is O(C)

    if ( maxValue < sum ) { // will be executed if the previous if is right so O(c')

        maxValue = sum ; // will be exceuted if the previous if is right so O(c')

    }

    return ; // will be executed once so O(1)

}

findMax (n - > leftChild , sum + n - > value ) ; // visiting every left child of each node

findMax (n - > rightChild , sum + n - > value ) ; // visiting every right child of each node 

// so we are visiting every node at least once if we have n node and m connections(edges) between nodes we have:
// O(n+m+C(c'+c'+1))=O(n+m) + O(K)

推荐阅读