怎么用自己的电脑做网站服务器,深圳app开发,医院网站建设滞后,梧州房地产信息网官网没有学习过数据结构算法之类专业毕业的#xff0c;因为特地学习了下#xff0c;收货挺多#xff0c;记录下~ 我们编写计算机程序的目的是解决我们实际的应用问题 首先 计算机科学研究的是什么 计算机科学不仅仅是对计算机的研究 计算机科学主要研究的是问题、问题解决过程以…没有学习过数据结构算法之类专业毕业的因为特地学习了下收货挺多记录下~ 我们编写计算机程序的目的是解决我们实际的应用问题 首先 计算机科学研究的是什么 计算机科学不仅仅是对计算机的研究 计算机科学主要研究的是问题、问题解决过程以及问题的解决方案 为了更好地处理机器相关性或独立性引入了抽象的概念 那么什么是抽象呢我们举个例子 比如说汽车从司机观点来看汽车是一台可以带人去往目的地的代步工具 从抽象角度说司机看到汽车的逻辑层次 这些操作机构方向盘、油门、挡位就称为“接口Interface” 抽象我们可以通过编程实现 而编程是通过一种程序设计语言将抽象的算法实现为计算机可以执行的代码的过程没有算法编程无从谈起 图灵奖获得者Niklaus Wirth的著名公式算法数据结构程序 程序设计语言需要为算法的实现提供实现过程和数据的机制具体表现为控制结构和数据类型 程序设计语言均有语句对应控制结构比如说顺序处理、分支选择、循环迭代 程序设计语言也提供最基本的数据类型来表示数据比如整数、字符等等对于复杂问题而言直接使用这些基本数据类型不利于算法的表达
因此我们引发出来一种抽象数据类型ADTAbstract Data Type,ADT是对数据进行处理的一种逻辑描述并不涉及如何实现这些处理并且它建立了一种对数据的封装封装技术将可能的处理实现细节隐蔽起来能有效的控制算法的复杂度
同一个ADT可以采用不同的数据结构来实现采用程序设计语言的控制结构和基本数据类型来实现ADT所提供的逻辑接口对数据实现“逻辑”层次和“物理”层次的分离可以定义复杂的数据模型来解决问题而不需要立即考虑次模型如何实现
刚提到了接口我们也可以理解为接口的两端就是抽象与实现
由于对抽象数据类型可以有多种实现方案独立于实现的数据模型通过层层抽象降低问题解决过程的复杂度~
我们为什么要学习和研究算法呢
首先我们就是在学习各种不同问题的解决方案其次各种算法通常有较大的差异在某些情况下当我们遇到棘手的难题某些问题解决需要一些折中的处理方式
什么是算法分析
算法是对问题解决的分步描述程序则是采用某种编程语言实现的算法同一个算法通过不同的程序员采用不同的编程语言能产生很多程序比较程序的好坏有很多的因素比如说代码风格、可读性等等而我们主要感兴趣的是算法本身的特性 算法分析主要就是从计算资源消耗的角度来评判和比较算法——更高效利用计算资源或者更少占用计算资源的算法就是好算法。
何为计算资源
一种是算法解决问题过程中需要的存储空间或内存但是存储空间受到问题自身数据规模的变化影响要区分那些存储空间是问题本身描述所需哪些是算法占用不容易另一种是算法的执行时间我们可以对程序进行实际运行测试获得真实的运行时间在python中我们可以通过time来打印出程序运行的开始结束时间 但是关于运行时间的检测实际上这样是不全面的同一个算法采用不同的编程语言编写放在不同的机器上运行得到的运行时间也会不一样有时候会大不一样因此我们需要更好的方法来衡量算法运行时间。
大O表示法
一个算法所实施的操作数量或步骤数可作为独立于具体程序/机器的度量指标 赋值语句是一个合适的选择 问题规模影响算法执行时间
问题规模影响算法执行时间的主要因素在前n个整数累计求和的算法中需要累计的整数个数合适作为问题规模的指标算法分析的目标是找出问题规模会怎么影响一个算法的执行时间 数量级函数 Order of Magnitude基本操作数量函数T(n)的精确值并不是特别重要重要的是T(n)中起决定性因素的主导部分 - 数量级函数描述了T(n)中随着n增加而增加速度最快的主导部分称作”大O“表示法记作O(f(n))其中f(n)表示T(n)中的主导部分 例如
T(n) 1n 当n增大时常数1在最终结果中显得越来越无足轻重所以可以去掉1保留n作为主要部分运行时间的数量级就是O(n)
再比如 T(n)5n^227n1005 当n很小时常熟1005起决定性作用 但当n越来越大n^2项就越来越重要了其他两项对结果的影响越来越小 同样n^2项中的系数5对于其增长速度来说也影响不大 所以可以在数量级中去掉27n1005以及系数5的部分确定为O(n^2)
影响算法运行时间的其他因素
有时决定运行时间的不仅是问题规模某些具体数据也会影响算法运行时间分为最好、最差和平均情况平均状况体现了算法的主流性能对算法的分析要看主流而不被某种特定的运行状况所迷惑
常见的大O数量级函数 通常当n很小的时候难以确定其数量级 当n增长到较大时容易看出其主要变化量级比如说对数、常数、线性、平方、立方、指数
其他算法复杂度表示法 大O表示法表示了所有上限中最小的那个上限
大Ω表示法表示了所有下限中最大的那个下限
大表示法如果上下限相同,那么就可以用大
变位词的判断问题
所谓”变位词“是指两个词之间存在组成字母的重新排列关系 如heart和earthpython和typhon 为了简单起见假设参与判断的两个词仅由小写字母构成而且长度相等 解题目标写一个bool函数以两个词作为参数返回这两个词是否变位词 解法一逐字检查 问题规模包含字符个数是n 且主要部分在于两重循环 所以总的执行次数是12345…n所以数量级是0(n^2)
def anagramSolution1(s1, s2):alist list(s2)pos1 0stilloK Truewhile pos1 len(s1) and stilloK:pos2 0found Falsewhile pos2 len(alist) and not found:if s1[pos1] alist[pos2]:found Trueelse:pos2pos21if found:alist[pos2] Noneelse:stilloK Falsepos1 pos11return stilloK
print(anagramSolution1(python,typhon))解法二 排序比较将两个字符串都按照字母顺序排好序再逐个字符对比是否相同如果相同则是变位词有任何的不同就不是变位词
def anagramSolution2(s1, s2):alist1 list(s1)alist2 list(s2)#转为列表alist1.sort()alist2.sort()pos 0#分别排序matches Truewhile pos len(s1) and matches:if alist1[pos] alist2[pos]:pos pos1else:matches Falsereturn matchesprint(anagramSolution2(python,typhon))解法三 暴力法穷尽一个所有可能的组合将S1出现的字符进行全排列再查看S2是否出现在全排列列表中这里最大的困难是产生S1所有字符的全排列对于越长的字符串所需的时间和复杂度也越来越大因此暴力法恐怕不算是一个好的算法
解法四 计数比较对比两个词中每个字符出现的次数如果26个字母出现的次数都相同的话这两个字符串就一定是变位词 具体做法为每个词设定一个26位的计数器先检查每个词在计数器中设定好每个字母出现的次数计数完成后进入比较阶段看两个字符串的计数器是否相同如果相同则两个字符串是变位词 计数比较中有3个循环迭代但不像解法1那样存在嵌套循环 前两个循环用于对字符串进行计数操作次数等于字符长度n 第3个循环用于计数器比较操作总次数是26次 所以总的操作次数T(n) 2n26其数量级为O(n)这是一个线性数量级的算法是4个变位词判断中性能最优的
def anagramSolution4(s1, s2):C1 [0]* 26C2 [0]* 26for i in range(len(s1)):pos ord(s1[i])- ord(a)C1[pos] C1[pos] 1for i in range(len(s2)):pos ord(s2[i]) - ord(a)C2[pos] C2[pos] 1stilloK Truej 0while j 26 and stilloK:if C1[j] C2[j]:j j1else:stilloK Falsereturn stilloKprint(anagramSolution4(apple,pleap))值得注意的是本算法依赖于两个长度为26的计数器列表来保存字符计数这相比前3个算法需要更多的存储空间牺牲存储空间换取运行时间或者相反这种在时空之间的取舍和权衡在选择问题解法的过程中经常会出现。
