算法:
数据结构与算法的关系是相互依赖不可分割的。
算法的定义:算法是解决特定问题求解步骤的描述,在计算机中为指令的有限序列,并且每条指令表示一个或多个操作。
算法的特性:有穷性、确定性、可行性、输入、输出。
算法设计的要求:正确性、可读性、健壮性、高效率和低存储量需求。
算法特性与算法设计容易混,需要对比记忆。
算法的度量方法:事后统计方法(不科学、不准确)、事前分析估算方法。
在讲解如何用事前分析估算方法之前,我们先给出了函数渐近增长的定义。
算法的时间复杂度和空间复杂度
函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n > N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于g(n)。于是我们可以得出一个结论,判断一个算法好不好,我们只通过少量的数据是不能做出准确判断的,如果我们可以对比算法的关键执行次数函数的渐近增长性,基本就可以分析出:某个算法,随着n的变大,它会越来越优于另一算法,或者越来越差于另一算法。
然后给出了算法时间复杂度的定义和推导大O阶的步骤。
推导大O阶:
用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中,只保留最高阶项。
如果最高阶项在且不是1,则去除与这个项相乘的常数。
存得到的结果就是大O阶。
通过这个步骤,我们可以在得到算法的运行次数表达式后,很快得到它的时间复杂度,即大O阶。同时我也提醒了大家,其实推导大O阶很容易,但如何得到运行次数的表达式却是需要数学功底的。
接着我们给出了常见的时间复杂度所耗时间的大小排列: 如图
- 大小: 19.6 KB
分享到:
相关推荐
挑战程序设计竞赛2 算法和数据结构.pdf
算法和数据结构算法与数据结构算法和数据结构算法与数据结构算法和数据结构算法与数据结构算法和数据结构算法与数据结构算法和数据结构算法与数据结构
学习数据结构的软件 和好用的 真的利于学习 算法和数据结构 希望大家看看 好好看吧 些的够多的了不说学习数据结构的软件 和好用的 真的利于学习 算法和数据结构 希望大家看看 好好看吧 些的够多的了不说学习数据结构...
挑战程序设计竞赛 2 算法和数据结构 渡部有隆 人民邮电出版社
《挑战程序设计竞赛2:算法和数据结构》,作者:渡部有隆、支鹏浩。高清带目录PDF,附带每章节源代码。
acm竞赛常用算法和数据结构
国外经典算法和数据结构 (共3部)part3
东北大学算法和数据结构课件东北大学算法和数据结构课件东北大学算法和数据结构课件东北大学算法和数据结构课件东北大学算法和数据结构课件东北大学算法和数据结构课件东北大学算法和数据结构课件
详细的算法和数据结构新手班
Golang算法和数据结构
经典的算法和数据结构教程汇总 希望对大家有帮助
讲解算法和数据结构的好书 本书较为详细和系统的讲解了算法和数据结构相关基础知识
数据结构是在计算机中组织和存储数据的一种特殊...算法和数据结构是计算机学习的基石。无论你学习计算机的任何方向,没有扎实的算法和数据结构,肯定学习起来就捉襟见肘了。这是基于 JavaScript 的算法和数据结构教程。
算法和数据结构代码
算法和数据结构ppt课件.ppt
大厂算法和数据结构刷题java实现