编程C,C ++,Java,PHP,Ruby,图灵,VB
计算机科学加拿大 
编程C,C ++,Java,PHP,Ruby,图灵,VB  

用户名:    Password: 
  登记 登记    
 递归算法图的时间复杂性
指数 -> 一般编程
查看上一个主题 可打印的版本下载主题订阅本主题私人信息 刷新页面 查看下一个主题
作者 信息
加里威




 邮政 发布: 星期二2013年2:30  帖子主题:递归算法图的时间复杂性

screen.width-200)this.width = (screen.width-200)" onclick="javascript:window.open('http://puu.sh/5I2s0.png','','scrollbars=1,toolbar=0,resizable=1,menubar=0,directories=0,status=0')" alt="发布图像,可能已经减少了大小。点击图片以全屏观看。" title="发布图像,可能已经减少了大小。点击图片以全屏观看。" />

我知道循环的前2个是O(n ^ 2),然后是循环的第三个是o(2m),然后我们有递归部分的IF语句。

所以它会是f(n)= n ^ 2 + 2m * f(n-1)吗?我显然省略了不断的时间。所以我猜基壳是f(1)= k。但答案是O(n ^ 3)。我不知道我在做什么......任何帮助吗?
此外,类似的问题

screen.width-200)this.width = (screen.width-200)" onclick="javascript:window.open('http://puu.sh/5I2tu.png','','scrollbars=1,toolbar=0,resizable=1,menubar=0,directories=0,status=0')" alt="发布图像,可能已经减少了大小。点击图片以全屏观看。" title="发布图像,可能已经减少了大小。点击图片以全屏观看。" />
所以它应该是f(n)= 2m * 2m * 2mn * f(n-1)和f(1)= k(不知道我正在做什么......我只是猜到这里)。答案是O(m ^ 2 * n)

8小时内的任何帮助都会受到赞赏
赞助
赞助
 赞助
 赞助
托尼




 邮政 发布: 星期二2013年12月2日2:45  帖子主题:RE:递归算法图的时间复杂性

您需要实际解决的价值 f(n-1)。但你已经知道它是什么!

如果 f(n)= n ^ 2 + 2m * f(n-1)
然后 f(n-1)=(n-1)^ 2 + 2m * f(n-2)
您可以重新进入原始方程式。

f(n)= n ^ 2 + 2m *((n-1)^ 2 + 2m * f(n-2))
继续,直到从等式的右侧删除f(),然后简化。
最新来自compsci.ca/blog: Tony's 编程博客 。 DWite - A. 编程竞赛.
加里威




 邮政 发布: 星期二2013年12月10日3:14 AM  帖子主题:Re:Re:递归算法图的时间复杂性

托尼@Tue 10月10日,2013年2:45写道:
您需要实际解决的价值 f(n-1)。但你已经知道它是什么!

如果 f(n)= n ^ 2 + 2m * f(n-1)
然后 f(n-1)=(n-1)^ 2 + 2m * f(n-2)
您可以重新进入原始方程式。

f(n)= n ^ 2 + 2m *((n-1)^ 2 + 2m * f(n-2))
继续,直到从等式的右侧删除f(),然后简化。

不确定如何“继续进行并简化”。第三个等式是:

f(n)= n ^ 2 + 2m [(n-1)^ 2 + 2m(n-1)^ 2 + 4m ^ 2f(n-3)],....究竟是什么是我的案件?我在这里没有看到一种模式..为什么这个方程如此乏味?这是在100马克3小时的最终考试中做多项选择问题的正确方法吗?因为我可能会在决赛中得到0%,然后哈哈
托尼




 邮政 发布: 2013年12月10日12:24 PM  帖子主题:RE:递归算法图的时间复杂性

我相信你有作业和致力于这样做的讲座。通过练习,它变得更加容易。

您知道此递归只能深入为n个级别。 f(n-2),f(n-3),...,f(n-n),在此时它以常数终止。
最新来自compsci.ca/blog: Tony's 编程博客 。 DWite - A. 编程竞赛.
从上一个显示帖子:   
    指数 -> 一般编程
查看上一个主题 告诉一个朋友可打印的版本下载主题订阅本主题私人信息 刷新页面 查看下一个主题

11  [ 4 Posts ]
跳到:    


Style:  
搜索: