题目
为什么合并排序算法时间复杂性T(n)=2T(n/2)+O(n)就会得出T(n)=nlogn
怎么通过T(n)=2T(n/2)+O(n)得出nlogn的呢,不懂nlogn是怎么来的
怎么通过T(n)=2T(n/2)+O(n)得出nlogn的呢,不懂nlogn是怎么来的
提问时间：2020-10-17
答案
画个图：
n
/
n/2 n/2
/ /
n/4 n/4 n/4 n/4
/ / / /
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
树高logn,每层加起来都是n,一共是logn×n
上面是n为2的幂时的特殊情况.对于一般情况,同样可证.
n
/
n/2 n/2
/ /
n/4 n/4 n/4 n/4
/ / / /
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
树高logn,每层加起来都是n,一共是logn×n
上面是n为2的幂时的特殊情况.对于一般情况,同样可证.
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
1,人们染上烟瘾,最终因吸烟使自己丧命.
最新试题
- 1一辆火车开过一座长为2430米的大桥用了150秒钟,开过一根电线杆只用了15秒钟,求火车长多少米?
- 2英语翻译
- 3“品质营造未来,细节决定成败”的英文翻译
- 4关于串联和并联的功率公式拜托了各位
- 5用介词填空 1.Where does Tom come____?2.what is the climate like————your country?
- 6罗马帝国的扩张对世界历史的发展影响
- 7colour changes是什么意思
- 8某地上年度电价为0.8元，年用电量为1亿度，本年度计划将电价调至0.55～0.75元之间，经测算，若电价调至x元，则本年度新增电量y（亿度）与（x-0.4）成反比例，又当x=0.65元时，y=0.8．
- 9求英语作文 就是我每天几点起床 怎么去学校 爸爸妈妈每天 几点 上班 怎么上班 65字左右不少于60 谢
- 10.帮我找一下这个方程式里的还原剂= =
热门考点
- 1wrong parameters!
- 2与数学式a=b或a≠c对应的C语言表达式
- 3甲数是X,比乙数的3倍多a,乙数是（ ） A（X＋a）/3 B3X-a C（
- 4仰视看量筒读数比实际值小?
- 5There are two _ over the river.填空,人教版.
- 6已知抛物线y=ax的平方-bx+c(a不等于0）与x轴交于点c(0,4),与x轴交于A,B两点,且点A的坐标为（4,0）求表
- 7我是2012年海南的考生,今年大概是这样!语文100,英语100,
- 8把下面的词语补充完整.顺便解一下那些形容人物动作,那些形容人物神态,那些形容人物精神
- 9two third 2/3如果加了连字符是不是two—thirds?加了连字符third为什么加了s?一般连字符表示数字,
- 10白兔比黑兔多100只,黑兔的只数是白兔的5分之3,白兔和黑兔各几只?（方程解,算术解）