|
知识路径: > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 > 数据结构与算法简介 >
|
相关知识点:5个
|
|
|
|
一般地说,设计一个“好”的算法应该考虑达到以下目标。
|
|
|
(1)正确性(correctness)。算法应该是满足具体问题的需求。
|
|
|
(2)可读性(readability)。算法主要是为了便于人的阅读和交流。可读性好的算法有利于人的理解。
|
|
|
(3)健壮性(robustness)。指的是,当输入数据非法时,算法也能适当地做出反应或对它进行处理,而不会产生莫名其妙的输出结果。
|
|
|
(4)效率和低存储量需求。效率指的是算法执行的时间。对于同一个问题,执行时间短的算法效率高。存储量需求指的是算法执行过程中所需要的最大存储空间。
|
|
|
一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上,所需资源越多,该算法的复杂性越高;反之,所需资源越少,该算法的复杂性越低。其中最重要的就是算法的时间复杂性和空间复杂性。
|
|
|
一般情况下,算法中的基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作
|
|
|
|
它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称做算法的渐进时间复杂度(Asymptotic Time Complexity),简称时间复杂度。被称为问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作。语句的频度(Frequency Count)指的是该语句重复执行的次数。
|
|
|
和算法的时间复杂度类似的,空间复杂度(Space Complexity)指的是算法所需存储空间的量度,记作:
|
|
|
|
其中,n为问题的规模或大小。根据算法的时间复杂度和空间复杂度,可以对算法进行评价。
|
|
|