我明天有一个计算机科学中期,我需要帮助确定这些递归函数的复杂性.我知道如何解决简单的案例,但我仍然在努力学习如何解决这些更难的案例.这些只是我无法弄清楚的一些示例问题.任何帮助将非常感谢,并将大大有助于我的学习,谢谢!
int recursiveFun1(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
int recursiveFun2(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
void recursiveFun4(int n, int m, int o)
{
if (n <= 0)
{
printf("%d, %d\n",m, o);
}
else
{
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
int recursiveFun5(int n)
{ …在任何情况下,您是否更喜欢O(log n)时间复杂度和O(1)时间复杂度？或O(n)到O(log n)？
你有什么例子吗？
如果我有一些R列表mylist,你可以obj像这样附加一个项目:
mylist[[length(mylist)+1]] <- obj
但肯定有一些更紧凑的方式.当我在R的新人时,我尝试这样写lappend():
lappend <- function(lst, obj) {
lst[[length(lst)+1]] <- obj
return(lst)
}
但是当然由于R的逐个调用语义而无法正常工作(lst在调用时有效复制,所以更改lst在范围之外是不可见的lappend().我知道你可以在R函数中做环境黑客攻击到达外部你的函数范围和mutate调用环境,但这似乎是一个大锤子写一个简单的追加函数.
任何人都可以建议一个更美丽的方式吗？奖励点,如果它适用于矢量和列表.
我相信有一种方法可以在O(n)中找到长度为n的未排序数组中的第k个最大元素.或许它是"预期的"O(n)或其他东西.我们应该怎么做？
我要显示log(n!)=Θ(n ·log(n)).
给出了一个提示,我应该用n n显示上限,并用(n/2)(n/2)显示下限.这对我来说似乎并不那么直观.那为什么会这样？我绝对可以看到如何将n n转换为n ·log(n)(即记录等式的两边),但这种情况是向后的.
解决这个问题的正确方法是什么？我应该绘制递归树吗？这没有任何递归,所以这似乎不是一个可能的方法..
我发现时间复杂度的资源还不清楚何时可以忽略时间复杂度方程中的项,特别是非多项式的例子.
我很清楚,给定n 2 + n + 1 形式的东西,最后两个术语是无关紧要的.
具体来说,给定两个分类,2 n和n*(2 n),是第二个与第一个相同的顺序？额外的n乘法是否重要？通常资源只是说x n处于指数状态并且增长得更快......然后继续前进.
我可以理解为什么它不会因为2 n将大大超过n,但因为它们没有被加在一起,所以在比较两个方程时它会很重要,实际上它们之间的差异总是n的因子,这似乎至少可以说是重要的.
我昨天在算法测试中遇到了这个问题,我无法找到答案.它让我绝对疯狂,因为它值得大约40分.我认为大多数课程都没有正确解决,因为我在过去24小时内没有提出解决方案.
给定长度为n的任意二进制字符串,如果存在,则在字符串中找到三个均匀间隔的字符串.编写一个在O(n*log(n))时间内解决此问题的算法.
所以像这样的字符串有三个"均匀间隔"的字符串:11100000,0100100100
编辑:这是一个随机数,所以它应该可以适用于任何数字.我给出的例子是为了说明"均匀间隔"的属性.所以1001011是一个有效的数字.1,4和7是均匀间隔的.
我的同事们带我回到了我的大学时代,今天早上讨论了排序算法.我们回忆起我们最喜欢的StupidSort,我们其中一个人确信我们已经看到了一种排序算法O(n!).这让我开始寻找可以找到的"最差"排序算法.
我们假设一个完全随机的排序会非常糟糕(即随机化元素 - 它是否按顺序排列？没有？再次随机化),我环顾四周,发现它显然叫做BogoSort,或者是Monkey Sort,或者有时只是随机排序.
Monkey Sort似乎具有最差的表现O(?),最好的表现O(n)和平均表现O(n·n!).
是否存在任何比平均性能更差的命名算法O(n·n!)？或者只是比一般的猴子排序更愚蠢？
我真的很困惑大O,大欧米茄和大Theta符号之间的差异.
我知道大O是上界,大欧米茄是下界,但大Ө(theta)究竟代表什么？
我读过它意味着紧张,但这意味着什么？
我在接受采访时被问及这是我提供的解决方案:
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
{
if (a[i] < b[j])
{
answer[k] = a[i];
i++;
}
else
{
answer[k] = b[j];
j++;
}
k++;
}
while (i < a.length)
{
answer[k] = a[i];
i++;
k++;
}
while (j < b.length)
{
answer[k] = b[j];
j++;
k++;
}
return answer;
}
有没有更有效的方法来做到这一点？ …