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

简介: 数据结构与算法「鱼C笔记一,谈谈算法,时间复杂度」教程参考自小甲鱼数据结构与算法视频,是个很不错的视频,感谢小甲鱼的付出相关代码已经上传到仓库的arithmetics文件夹为什么要学习算法因为好的算法可以提高程序的运行效率,我们从运行效率的方面来举例,1加到100。

数据结构与算法「鱼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)。

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

输入规模 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<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
    }
}
输入规模 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<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=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
目录
相关文章
|
22天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
58 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
19天前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
18天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
30 4
|
23天前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
30 1
|
23天前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
38 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
23天前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
11 0
|
24天前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
29 0
|
3天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
47 9
|
2天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
21 4
|
25天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
25 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器