荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: blackhawk (blackhawk), 信区: Program
标  题: Re: 贴答案了
发信站: 荔园晨风BBS站 (Thu Jan  5 13:29:20 2006) , 站内信件

第九个解答时间复杂度较高且较为复杂,
如果我们能够假设所有集合中的元素之间都是用逗号隔开,且元素这个字符串中
不会有逗号出现,则我们可以将一个集合整体视为一个字符串,
打个比方:集合一的逗号分别出现在0,5 ,10这些位置上,集合二的逗号分别出现在0,3这
些位置上,则模板匹配如果找到了逗号相隔相等的地方再开始比较,如果比较到了下一个逗
号处,则两个集合重叠,然后合并,再依次递推
所以估计整个算法的时间复杂度为O(求逗号的位置)+O(遍历)
前者的大概时间复杂度为O(元素个数*o(单个元素逗号查找时间)),
后者的平均时间复杂度为O(相同长度、但数值不同的元素的字符串匹配算法)

【 在 dynamic 的大作中提到: 】
: 一、简单题
: 这种问题,会的就不屑答,不会的就baidu一下. 这里略过了, sorry..
: 二、
: ////////////////////////////////////////////////////////////////////////
: /////////////////
: 6. 阶乘, code如下:
: # include <stdio.h>
: # include <math.h>
: # define MAX 100000
: int res[MAX];  //储存结果,每一个int保留4位整数,所以n!在4*MAX位以内时,
: 算法保证正确.
: int max_n()   //计算当内存是MAX时,可计算的n是多少.
: {
:         /*
:            n!的位数 = log10(n!) 取整后加1. 故
:            n!的位数 = log10(1)+log10(2)+...+log10(n)取整加1.
:            当然,也可以用Stirling逼近公式来计算,这样快好多,
:            不过考虑到贵公司的工程师数学水平有限,可能看不懂,
:            所以还是用这个方法来计算就算了.
:         */
: (以下引言省略...)

--

※ 来源:.荔园晨风BBS站 http://bbs.szu.edu.cn [FROM: 210.21.224.235]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店