数据结构与算法「鱼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")//输出
}
AI 代码解读

我们来看看执行次数

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

在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次
}
AI 代码解读

原本需要执行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")
}
AI 代码解读

我们获取开始时间,结束时间,算出程序运行的时间。运行结果未使用高斯算法的程序运行时间为: 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")
}
AI 代码解读

运行使用了高斯算法的程序运行时间为: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次
}
AI 代码解读

在该程序中,我们整个程序只执行了两次,一次是在输入字符串变量时,一次是在输出变量时。那么这样的算法程序,我们可以称它的时间复杂度为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")
}
AI 代码解读

在这段程序中,虽然我们输出了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
    }
}
AI 代码解读
输入规模 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
    }
}
AI 代码解读

还是用以上程序作为例子,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次
        }
    }
}
AI 代码解读

可以看做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
目录
打赏
0
0
0
0
1
分享
相关文章
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
102 1
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
83 29
|
22天前
|
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
83 25
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
63 23
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
76 20
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
54 2
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
100 1
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
354 9
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
56 1

热门文章

最新文章

  • 1
    局域网屏幕监控系统中的Python数据结构与算法实现
    135
  • 2
    2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
    49
  • 3
    2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    46
  • 4
    2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    52
  • 5
    2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    57
  • 6
    2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    41
  • 7
    2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    72
  • 8
    2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    39
  • 9
    2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    46
  • 10
    2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    45
  • AI助理

    你好,我是AI助理

    可以解答问题、推荐解决方案等