本文共 4353 字，大约阅读时间需要 14 分钟。
教程参考自小甲鱼数据结构与算法视频，是个很不错的视频，感谢小甲鱼的付出
相关代码已经上传到仓库的文件夹
因为好的算法可以提高程序的运行效率，我们从运行效率的方面来举例，1加到100。案例使用的是。
1）不使用算法
我们不使用算法优化，直接用for循环进行相加
fun main(args: Array) { var sum: Int = 0//总数 for (i in 1..100) {//遍历，从1加到100 sum + =i//sum和i相加 } println("$sum")//输出}
我们来看看执行次数
fun main(args: Array) { var sum: Int = 0//执行1次 for (i in 1..100) { sum += i//执行了100次 } println("$sum")//输出}
在for循环里面，执行了100次
2）使用算法
这里我们使用
fun main(args: Array) { var sum: Int = 0//执行1次 val n = 100//执行1次 sum = (1 + n) * n / 2//执行1次 println("$sum")//执行1次}
原本需要执行100次的任务，被我们1次就解决了
3）结论
当然，如果仅仅是这个案例，其实你觉得运行时间是差不多。我们稍微修改下代码，拿出证据。
fun main(args: Array) { //普通循环 val startTime = System.currentTimeMillis() //获取开始时间毫秒值 var sum = 0L//总数 for (i in 1..1000000000) {//遍历，从1加到10亿 sum += i//sum和i相加 } println("$sum")//执行1次 val endTime = System.currentTimeMillis() //获取结束时间毫秒值 System.out.println("程序运行时间： " + (endTime - startTime) + "ms")}
我们获取开始时间，结束时间，算出程序运行的时间。运行结果未使用高斯算法的程序运行时间为： 542毫秒。
fun main(args: Array) { //使用高斯算法 val startTime = System.currentTimeMillis() //获取开始时间 var sum= 0L//执行1次 val n = 1000000000000//执行1次 sum = (1 + n) * n / 2//执行1次 println("$sum")//执行1次 val endTime = System.currentTimeMillis() //获取结束时间 System.out.println("程序运行时间： " + (endTime - startTime) + "ms")}
运行使用了高斯算法的程序运行时间为：1毫秒
结论是使用算法确实能让我们的程序提高运行效率
一，大O计法
我们用时间复杂度来评估程序运行时间的需求，如上小节的程序运行时间。
上小节为证明算法价值测试了程序运行时间，但是很多时候我们是要把算法先设计好，才开始写代码。这也符合我们的正常思维，毕竟只有设计时觉得是个好算法你才会去把它写出来嘛。
这也就是我们说的事前分析估算方法
1）常数阶
我们用一种叫做大O计法来度量算法的时间优劣，大O计法使用了程序的执行次数来衡量程序的运行时间。
fun main(args: Array) { //输入字符串变量 val n = readLine()//执行一次 /** * 1，常数阶 * 将输入字符串n通过toInt方法转化为Int类型 * 而后面的?:1看起来是三元运算符，其实不是的，这是Kotlin的ELvis操作符。 * 它的作用是当检测到n变量的值为空时，使用默认值1 */ a(n?.toInt() ?: 1)}fun a(n: Int) { println("$n")//执行1次}
在该程序中，我们整个程序只执行了两次，一次是在输入字符串变量时，一次是在输出变量时。那么这样的算法程序，我们可以称它的时间复杂度为O(1)。
这种执行次数不会随着输入规模增长的算法我们称为常量阶。
| 输入规模 | 1 | 100 | 1000 | 10000 |
|---|---|---|---|---|
| 执行次数 | 2 | 2 | 2 | 2 |
那为什么明明是执行了两次，却称它的的时间复杂度是O(1)呢？因为在大O计数法里，常量阶不管执行多少次，都是写作1，比如
fun b(i: Int) { println("$i") println("$i") println("$i") println("$i") println("$i") println("$i") println("$i") println("$i")} 在这段程序中，虽然我们输出了8次，但是使用大O计法仍然是O(1)。
这个可以先记着，后面我们与线性阶，平方阶对比时会讲解为什么这样，其实就是大O计法里面有一个思想，忽略少数的误差，有点像是高中物理测试时的忽略误差。
当n变得很大，很大的时候，常数阶因为执行次数并不会增长，和其他会随着输入规模的增长而变大的阶对比来说，实在太小了，就近似看成是1
常量阶的计法永远是O(1)
2)线性阶
线性阶其实就是我们的一元一次函数，y=kx+b
/** * 线性阶 */fun main(args: Array) { //输入字符串变量 val n = readLine()//执行次数为1 /** * 1，线性阶 * 将字符串n通过toInt方法转化为Int类型 * 而后面的?:1看起来是三元运算符，其实不是的，这是Kotlin的ELvis操作符。 * 它的作用是当检测到n变量的值为空时，使用默认值1 */ c(n?.toInt() ?: 1)//常量阶1}fun c(n: Int) { //循环，从1到n for (i in 1..n) { println(i)//执行次数是1 }}
| 输入规模 | 1 | 100 | 1000 | 10000 |
|---|---|---|---|---|
| 执行次数 | 2 | 101 | 1001 | 10001 |
在这个函数中，输出执行次数为1n，输入执行次数为1，我们会下意识得以为计法是O(1n+1)。
还记得之前说过忽略吗，我们可以通过高中数学知识来帮助记忆，我们把线性阶看成是一元一次函数，y=kx+b，x是我们的输入规模，y为执行次数，kb为常数，在大O技数法中，kb不管多少，都是忽略b，把k看做1。我们的程序可以看做是y=1n+1，最后的计法是O(n)。
/** * 线性阶 */fun main(args: Array) { //输入字符串变量,这里相当于y=kx+b的b val n = readLine() val n2 = readLine() val n3 = readLine() val n4 = readLine() /** * 1，线性阶 * 将字符串n通过toInt方法转化为Int类型 * 而后面的?:1看起来是三元运算符，其实不是的，这是Kotlin的ELvis操作符。 * 它的作用是当检测到n变量的值为空时，使用默认值1 */ d(n?.toInt() ?: 1)//常量阶1}fun d(n: Int) { //循环，从1到n，这里的n相当于1元一次函数的y=kx+b的x for (i in 1..n) { //这里的输出次数相当于1元一次函数y=kx+b的k println(i)//执行次数是1 println(i)//执行次数是1 println(i)//执行次数是1 println(i)//执行次数是1 println(i)//执行次数是1 println(i)//执行次数是1 }}
还是用以上程序作为例子，y=6x+4，但是由于b要被忽略，k看做是，所以简化后还是y=x，记作时间复杂度为O(n)的算法
线性阶的计法永远是O(n)
3)平方阶
平方阶类似我们的一元二次方程，y=kx^2+bx+c
/** * 平方阶 */fun main(args: Array) { //输入字符串变量 val n = readLine()//执行了一次 /** * 1，常数阶 * 将字符串n通过toInt方法转化为Int类型 * 而后面的?:1看起来是三元运算符，其实不是的，这是Kotlin的ELvis操作符。 * 它的作用是当检测到n变量的值为空时，使用默认值1 */ a(n?.toInt() ?: 1)//常量阶1}fun a(n: Int) { for (i in 1..n) { for (j in 1..n) { println("$i,$j")//执行了n*n次 } }}
可以看做y=x2+1，记做O(n2)，忽略输入次数c
| 执行次数函数 | 记作 | 用语 | 解释 |
|---|---|---|---|
| 13 | O(1) | 常数阶 | 常数阶不管执行次数多少，都看做1 |
| 2n+3 | O(n) | 线性阶 | 线性阶可以看做y=kx+b，永远忽略b，k记做1 |
| 3n^2+2n+1 | O(n^2) | 平方阶 | 平方阶看做y=kx^n+bx+c，忽略bx+c，k记做1 |
转载地址：http://ptgfl.baihongyu.com/