复杂..大O

我必须确定以下函数的时间复杂度（大O）：复杂..大O

void BET::makeEmpty(BinaryNode* &n) 
{ 
    if(n != NULL) 
    { 
     makeEmpty(n->left); 
     makeEmpty(n->right); 
     delete n; 
    } 
    n = NULL; 
}

我所熟悉的时间，简单的复杂功能（for循环，嵌套循环等），但我不确定如何确定递归函数的大O.

谢谢！

来源

2014-03-29 sangam.saga

我认为你的问题的格式更适合于stackexchange网络的编程部门。 http://programmers.stackexchange.com/，是关于递归函数复杂性的一般问题。这听起来更具体一点，如果你在确定这种情况下的复杂性背景下概述了商业目的。没有任何实际用途的理论没有任何意义。说了这么多，看看这个：http://www.cs.duke.edu/~ola/ap/recurrence.html – Neolisk

那么，这一个比你想象的容易：makeEmpty执行一个常量（O(1)）的工作量（当然不包括递归调用）。它将在树中的每个节点上运行一次。所以它的时间复杂度是O(n)，其中n是树中节点的数量。

来源

2014-03-29 21:41:33 Benesh

所以只需O（n）将是答案？ –

@ user2267975是的！ –

@ user2267975：是的，每个节点将执行一次该操作，因为n节点将执行n次操作，所以它是O（n） –

我相信你的算法递推关系看起来应该像下面这样：

enter image description here

你能解决吗？

来源

2014-03-30 14:44:08

回答

相关问题