C-随机输入的递归函数的时间复杂性

Question

我是C编程的初学者，所以我需要一些帮助时间复杂性功能。

int function(int n)
{ if (n <= 1)
    return n;
int i = random(n-1);
return test(i) + test(n - 1 - i);
}

我不知道该如何处理这个问题，因为具有o(1(复杂性的随机函数返回随机数字。

Answer 1

我不知道该如何处理这个问题，因为具有o(1(复杂性的随机函数返回随机数字。

很明显，您将random(n-1)称为简单(恒定时间(调用。孤立地进行直接的。有趣的是，呼叫返回的值对性能有什么影响。

• 提示：首先考虑算法的最佳案例和最差案例性能。

• 提示：为了进行分析，请考虑一个假设版本的random，该版本生成一个数字序列，该序列是随机数的对立面： - (