数据结构与算法之算法分析
算法的五个重要特征：有穷性，确定性，可行性，输入，输出。
输入，是指算法具有零个或多个输入。
输出，是指算法至少有一个或多个输出。
有穷性，是指算法在执行有限的步骤之后，自动结束而不是出现无限循环，并且每一个步骤在可接受的时间内完成。
确定性，是指相同输入只能有一个唯一的输出结果，不会出现二义性。
可行性，是指算法每一步骤都必须可行，能够通过有限的执行次数完成。
好的算法更考虑效率和空间占用（时间复杂度和空间复杂度），通常复杂度更多描述的是一个量级而不是具体的数字。
时间复杂度
算法的时间复杂度，也就是算法的时间量度，记作： T(n)=O(f(n))。它表示随问题规模 n的增大算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中 f(n)是问题规模 n的某个函数。
计算方法：
1.用常数1取代函数中所有的常数
2.只保留最高项
3.最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。
常数阶：一般不涉及循环操作的都是常数阶，因为它不会随着n的增长而增加操作次数。
线性阶：一般含有非嵌套循环涉及线性阶，线性阶就是随着输入规模的扩大，对应计算次数呈直线增长
平方阶：一般嵌套循环属于这种时间复杂度
立方阶：一般三层嵌套循环属于这种时间复杂度
对数阶：对于对数阶，由于随着输入规模n的增大，不管底数为多少，他们的增长趋势是一样的，所以我们会忽略底数。
空间复杂度
空间复杂度概念:是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))、
算法的空间复杂度是通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作： S(n)=O(f(n))S(n)=O(f(n)) S(n) = O(f(n))S(n)=O(f(n)) 。其中，n 为问题的规模， f(n)f(n) f(n)f(n) 为语句关于 n 所占存储空间的函数。
ゝ一纸荒年。
「爱情、让人受尽委屈。」
傷城~
还没有评论，来说两句吧...