算法与数据结构:探索基本概念
发表时间: 2023-01-11 14:01
是指数据对象中数据元素之间的相互关系
存储结构,是指数据的逻辑机构在计算机中的存储形式
目的是将数据及逻辑关系存储到计算机的内存中
是指一个数学模型及定义在该模型上的一组操作
体现了程序设计中问题分解、抽象和信息隐藏的特性
算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作
输入、输出、有穷性、 确定性 、可行性
定义:表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度
用大写O( )来体现算法时间复杂度的记法,我们称之为大O记法。
推到大O阶的方法:通过观察和计算,得出运算中的次数,是否有嵌套和循环,考察的是数列的能力
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n )<O(n!)<O(nn)
通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)=O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数