如何找到此代码的时间复杂度

本文介绍了如何找到此代码的时间复杂度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

int fun（int n） { if（n< = 1）返回1; 返回乐趣（n-1）+乐趣（n-2）; }

我的尝试：

int fun2（int n） { if（n< = 1）return n; 返回fun2（n-1）+ fun2（n-1）; }

此代码的时间复杂度为::: O（2 ^ n） 在此代码函数中返回fun2（n-1）+ fun2（n-1）即两者相同 但如果两者不同，如何找到时间复杂度

解决方案

该代码看起来像递归的Fibonacci函数。 由于函数中的代码非常简单，因此时间和复杂度主要取决于函数调用的数量。 br /> 最简单的方法是计算函数调用。 声明一个全局变量用作计数器，在函数中添加一行，在每次调用时递增值。 然后收集每个 n 值的调用次数，创建一个包含该值的表，并比较每个名词

int fun(int n) { if (n <= 1) return 1; return fun(n-1) + fun(n-2); }

What I have tried:

int fun2(int n) { if (n <= 1) return n; return fun2(n-1) + fun2(n-1); }

time complexity for this code is::: O(2^n) In this code function is returning fun2(n-1) + fun2(n-1) i.e.both are same But how to find time complexity if both are different

解决方案

That code look furiously like a recursive Fibonacci function. Since the code in function is very simple, the time ans complexity mainly depend in the number of function calls. The easiest thing to do is counting function calls. Declare a global variable to use as counter, add a line in function that increment the value on every call. Then collect the number of calls for each value of n, make a table with the value and compare how number of calls evolve with each n.