如果我有一个简单的递归算法,比如:
numberOfMatches(A, x, i): // A is an array of values, x is a single value
the algorithm will search the array from A[1] to A[i]
count = 0
if i==0:
return 0
if A[i]=x:
count = numberOfMatches(A, x, i-1) +1
else:
count = numberOfMatches(A, x,
我目前正在观看关于算法的开放式视频课程,在第二节课中,我停留在教授通过归纳来证明以下观点的时候:
n=O(1)
proof:-
For base case
1=O(1)
suppose n-1 = O(1)
=> 1+(n-1)=O(1)+O(1)
=> n=O(1).
hence it is proved.
但这位教授告诉我们,我们不能接受“大O”,上面的证明不是真的,但为什么呢?
如何计算下列函数的时间复杂度?
int Compute (int n)
{
int j = 0;
int i = 0;
while (i<=n)
{
i = 2*j + i + 1;
j++;
}
return j-1;
}
现在,我知道循环具有O(n)时间复杂度,但在这种情况下,i的增长速度要快得多。通过迭代迭代,我发现,对于每一个m次迭代,i = m^2.但我仍然很困惑如何计算大O。
我希望为类似RSA的加密算法解决这个模算子问题(不完全相同),但我不习惯使用模运算符。
我有四个价值观,这就是我发现的最佳值。有一条消息,一个密码和两个密钥(公共和私有)。消息= m,密码= c,公钥= n,私钥= e。最后,我将同时拥有密钥和密码,而不是消息。
对于我最初的加密公式,我使用了:
c = (m + e) % n
为了解密,我使用了这个:
m = (c - e) % n
但当我决定用乘法和除法替换加减时,事实证明并不那么简单:
c = (m * e) % n
m != (c / e) % n
最后,我希望取得以下第一项成果:
c = (m ** e) % n
总之,我有c = 8
我正在学习“大O”( Big ),并且被一个问题困住了。
问题-
int sample_function (int x) {
if (x<1){
return x;}
int y = x/2;
return sample_function (y) + sample_function (x-y);
}
如果我们调用(n/2)的2个递归调用,那么大O会是什么?我知道除法递归函数(n/2)的大O是O(log(n)),但不确定这个问题。