数据结构与算法「鱼C笔记一，谈谈算法，时间复杂度」

数据结构与算法「鱼C笔记一，谈谈算法，时间复杂度」

教程参考自小甲鱼数据结构与算法视频，是个很不错的视频，感谢小甲鱼的付出

相关代码已经上传到仓库的arithmetics文件夹

为什么要学习算法

因为好的算法可以提高程序的运行效率，我们从运行效率的方面来举例，1加到100。案例使用的是Kotlin语言。

1）不使用算法

我们不使用算法优化，直接用for循环进行相加

fun main(args: Array<String>) {
    var sum: Int = 0//总数
    for (i in 1..100) {//遍历，从1加到100
        sum + =i//sum和i相加
    }
    println("$sum")//输出
}

我们来看看执行次数

fun main(args: Array<String>) {
    var sum: Int = 0//执行1次
    for (i in 1..100) {
        sum += i//执行了100次
    }
    println("$sum")//输出
}

在for循环里面，执行了100次

2）使用算法

这里我们使用高斯算法

fun main(args: Array<String>) {
    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<String>) {
    //普通循环
    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<String>) {
    //使用高斯算法
    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<String>) {
    //输入字符串变量
    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)。

这种执行次数不会随着输入规模增长的算法我们称为常量阶。

那为什么明明是执行了两次，却称它的的时间复杂度是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<String>) {
    //输入字符串变量
    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
    }
}

在这个函数中，输出执行次数为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<String>) {
    //输入字符串变量,这里相当于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<String>) {
    //输入字符串变量
    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=x^{2+1，记做O(n}2)，忽略输入次数c