时间复杂度

来自计算思维百科
跳转至: 导航搜索
时间复杂度.png

时间复杂度(Time Complexity)度量一个算法(一系列解决问题的清晰指令和规则)解决问题所需的时间。我们常常用这个指标来衡量算法的性能优劣,一般地,时间复杂度越低,算法性能越好。

基本概念

算法的时间复杂度并不是算法解决问题所需的时间,而是指运用该算法解决问题的过程中最主要步骤的执行次数,我们叫做计算工作量。因为影响算法解决问题所需时间的因素很多,除了算法本身和问题的难易程度之外,还与负责解决问题的人或者计算机本身配置有关。所以,往往一个算法给不同的人或者计算机使用,解决问题的时间也有很大差别,我们利用时间复杂度只是为了比较和评价,解决同一个问题,哪个算法快,哪个慢,这取决于算法中的计算工作量。

应用范围

算法的时间复杂度衡量算法解决问题快慢程度,我们常常用它来评价和选择更优的算法。

使用方法及步骤

算法的时间复杂度的计算其实是计算该算法解决问题的过程中最主要步骤的执行次数。每个问题都有最好、最坏的情况,所以计算算法的时间复杂度时,我们也要根据不同的情况进行讨论。

应用案例

应用1-选择手套

案例:在一个抽屉里有22只手套:5双红手套、4双黄手套和2双绿手套。你在黑暗中挑选手套,而且只能在选好之后才能检查它们的颜色。在最好的情况下,你最少选择几只手套就能找到一双匹配的手套?在最差的情况下呢?

 

解决步骤: 要找到一双匹配的手套,算法就是挑选手套,主要执行步骤就是“挑选”,所以挑选的手套只数就是该算法的时间复杂度。在最好的情况下,我们只需要挑选2只手套就能匹配,即最优情况下,算法时间复杂度是2;在最坏的情况下,我们需要挑选4只手套就一定能得到一双同样颜色的手套,即最坏的情况,算法时间复杂度是4。在这个例子中我们衡量算法的时间复杂度没有测量我们挑选手套的时间,而是计算主要步骤“挑选”的次数。

应用2-评“科目一机考”试卷

案例:驾照科目一考试是机考选择题,考生在计算机上答题然后提交答案,每个考生的题目数量都是100道题目,但是题目内容不一样。考生答题速度不同,那么评分系统给出分数的时间也不同,但是因为系统评分的主要操作就是将考生答案与系统答案进行比较,而固定的100道题目,比较操作也是固定的100次,所以评分系统评试卷的时间复杂度固定为100,并不会受考生的答题速度影响。

应用2-寻人顺序对算法的影响

案例:假设我们要在全世界搜索“范冰冰”,搜寻条件的顺序设置有很多种方式,

方式一:

  1. 是中国人吗?这个条件在全世界范围内筛选出13亿人供下个条件选择
  2. 是演员吗?这个条件在全国范围内筛选出10万人供下个条件选择
  3. 是女性吗?这个条件在全国演员中筛选出5万人供下个条件选择
  4. 演过电视剧《武媚娘传奇》吗?这个条件在全国女性演员中筛选出100人供下个条件选择
  5. 演过《还珠格格》吗?找出范冰冰

方式二:

  1. 演过《还珠格格》的最漂亮的女演员是谁?找出范冰冰

从上述两种方式的对比可以看出,解决同一个问题的不同算法时间复杂度是大大不同的。

可以体现的计算思维

算法时间复杂度是衡量算法好坏的重要指标。将算法主要步骤执行次数抽象成时间复杂度,利于我们对解决问题的算法进行评估选择并加以改良。时间复杂度体现了计算思维的抽象特点。