大佬教程收集整理的这篇文章主要介绍了【万字长文】不学算法你也应该知道的算法知识,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
兄弟c;想一起学习算法吗?想一起变强吗?想毕业的时候在算法方面吊打面试官吗?想成为刷题狂人吗?
我的伙伴c;刷题四天王(自己封的):
英雄大哥
吒老二
扣三
菜鸟的我
那还等啥!算法那还不得赶紧学起来!这一激动我这包整的河南话都彪出来了。
什么是算法?我们为什么要学算法?算法是为了什么才出现的?算法是怎么从解决一个问题慢慢到解决一个体系的问题的?
想要学习算法c;如果你要求不高c;你可以不学这个c;你只需要知道怎么用c;如何用c;什么地方用就可以了~
但是如果你对算法想有深入的了解c;那么这些你是需要知道的。
想必大家都听过这样一句话:数据结构+算法=程序
你可能会说:屁嘞c;我不会数据结构与算法c;我也照样写程序。我只能说:能说出来这话c;一看你就是个新手!
你了解什么是数据结构吗?你了解什么是算法吗?不要把它们看得那么高大上c;他们的原本定义其实很简单的~~
提一嘴基础知识c;在编程语言中c;数据是信息的载体c;而数据又分为值类型和引用类型。值类型无非就是整数c;实数c;复数等c;而引用类型就是那些数组c;字符串c;集合图片c;音乐等。
有位老哥说过:任何数据都可以使用数据结构表现出来。其实意思就是c;数据结构就是存储数据的结构体。
其实数据结构的定义就是这么简单c;不要看的太高
一个程序c;有一种书本上的描述:解决一个问题除了要有一个数据结构来表示和组织信息外c;还需要一系列步骤来完成问题的解决方案。
当然了c;第一个逗号前面的那当然就是数据结构了c;那后面的一系列步骤其实说的就是算法。
也可以称为:操作数据结构的方法;或者称为:解决问题的方案。
有点模糊也没关系c;我来带你看几个例子c;你就明白了~~
例子1 HelloWorld:
HelloWorld也能当数据结构与算法的例子??!没错c;没看错c;他能!他能!!
java代码:
public class Hello{ /* 在这里Hello和World就是两个数据结构 将两个数据结构用+拼接起来c;就是算法 */ public static void @H_833_125@main(String[] a){ System.out.println("hello"+"World"); } }
Python代码:
print("hello"+"World")
同理
例子2 两个数字相加:
输入两个数字c;输出两个数字的和
Java代码:
public class Hello{ public static void @H_833_125@main(String[] a){ System.out.println(sumTwo(5,6)); } public static int sumTwo(int a, int b){ return a+b; } }
这里面没有数据结构c;只有时间c;也有算法c;算法就是a+b
Python代码:
def sumTwo(a:int,b:int)->int: return a+b
例子3 两数之和(来真的了啊!):
给你一个非空数组c;和一个目标值c;从数组中找出两个元素使其的和与目标值相同c;并返回一个长度为2的数组装这两个值对应的下标c;只允许一个元素使用一次
————源于力扣第一题c;简单难度
Java代码:
public class Hello{ public static void @H_833_125@main(String[] a){ System.out.println(); } public static TwoSum(int[] nums1, int[] nums2, int target){ /* 最容易想到的c;也是没学过系统学习过算法的人的方法 嵌套循环: 遍历nums1c;再遍历nums2c;然后求和c;与目标值做判断 当然c;想法很简单c;却会出错c;因为还要考虑元素只用到一遍 */ for (int i=0;i<nums.length;i++){ for (int j=0;j<nums.length;j++){ if (i!=j){ if (nums[i]+nums[j]==target){ return new int[]{i, j}; } } } } return null; } }
这里面就用到了一个数据结构c;叫做数组c;这里的算法就是将新数组求出来的过程!
Python代码:
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(len(nums)): if i==j: conTinue elif nums[i]+nums[j]==target: return [i, j]
当然c;例3的方法是很简陋的c;更简单的方法还有哈希法和二分法c;在这道题中c;哈希法的时间复杂度是O(n)c;二分法的时间复杂度为O(nlogn)
感兴趣的话c;可以看看我的这一篇博客:零基础的我刷力扣一周后c;总结了点东西
这三个例子大概也能让你对什么是数据结构与算法有一个大致的了解了。那么接着看吧~
那么为什么公司喜欢会算法的人呢?换句话说c;为什么会算法的人会更吃香呢?
因为公司运行你的代码是需要机器的c;而机器也是分价钱的c;如果你的算法很糟糕c;那就会让公司的机器运行起来占用CPU资源多c;拟人化一下那就是会很吃力c;而且运行你得代码会更耗费时间。
而算法的出现也是因为先有了问题c;之前也说过算法是什么了c;就是一个问题的解决方案c;所以我们的算法是为了解决问题才出现的。
当然一个问题都是可以由多个算法解决的。俗话说c;无规矩不成方圆。
那么不同的算法是不是得有相同的规则c;或者说相同的特性c;才能约束算法c;不能任意一种算法就可以解决问题。
打个比方c;就用曹冲称象这个例子吧。为了不浪费大家的脑子c;我决定就说的简单一点。
现有大象一头c;需要知道大象有多重。但是秤太小c;无法精准测量。
请你设计一个算法来计算大象的重量。
曹冲的方法:把象放到大船上c;在水面所达到的地方做上记号c;再让船装载其它东西c;称一下这些东西,那么比较下就能知道了。
方法1:我把大象切碎c;一块一块量
方法2:造一个超大的秤c;专门用来秤大象的重量
你觉得方法1和方法2怎么样?先不急着回答c;我们先看看算法的这几个性质。
一个算法必须要有一个明确的终止条件来控制处理过程的终止c;或者说结束。
什么意思呢?就是你的算法至少要有一个终止条件c;或者说能够在特定时间内终止c;并计算出结果。要不然你的方法有什么意义呢?
你的算法的没一个步骤都是可以被机器或者人执行的。
你的算法所计算的结果是能够用来解决这个问题的。
那么c;在看完这四个特性后你怎么回答上面的问题呢?
当然c;答案我也在特性里面说了出来c;还不知道答案的c;面壁思过去!
那么讲了这么多c;我们怎么判断我们的程序是好是坏呢?那就是时间复杂度和空间复杂度。
是不是感觉这两个名词好难理解?没事c;他其实也不难。
所谓时间复杂度就是算法执行的时间。而时间复杂度可以由两种方式:
- 计算程序实际运行时间
- 计算程序相对运行时间
我们知道c;即使是同一种算法c;在不同的编程语言c;不同的机器c;不同的环境索引行的实际时间也是不一样的。
所以第一种方式c;就不是很银杏化!那么就只能是第二种方法了来判断我们的程序是否得到了优化~~
而时间复杂度又分为三种c;最优情况c;最劣情况c;平均情况。而这个情况是由问题来决定的~
这三种情况我就不多说啦~看名字就知道了
时间复杂度统一使用O(X)来表示c;也是俗称的大O表示法c;而时间复杂度的大小与问题有关。
比方说:
- 我给你三个数c;你把他们三个从小到大排序c;时间复杂度是O(3)c;也可以说是 O(1)
- 我给你10**100个数c;你把他们从小到大排序c;时间复杂度是O(10**100)c;也可以近似取到O(1)
- 我给你几个数c;你把他们从小到大排序c;时间复杂度为O(n)
那么为什么改了一下题目c;时间复杂度就不一样了呢?因为1c;2是确定的值c;不会受到外部影响而改变c;所以只需要循环那么多次c;不会改变所以时间复杂度是O(1);而3不一样c;他给的值是不确定的c;所以需要循环n次c;时间复杂度就是O(n)
当然这个也是可以根据问题改变的c;那就是对特定的值使用特定的算法。比如二分法c;递归的时间复杂度就是O(logn)c;而O(n)是大于O(logn)的
而如果需要嵌套循环c;那么可能是O(n**2)或者O(nlogn)。
常见的时间复杂度按照从小到大的顺序排列有:O(1)c;O(logn)c;O(n)c;O(nlogn)c;O(n**2)c;O(2**n)c;O(n!)
根据算法在执行过程所使用的存储空间c;分为堆区和栈区c;当然还有别的区。
而栈区中存放着变量名c;堆区中存放着变量名指向的值。这么说可能不好理解c;那就画个图吧~~
诶😱😨叭叭了这么多c;好像还没到点上!
稍安勿躁嘛~~
这就来空间复杂度啦~
其实和时间复杂度差不多c;我们使用常数c;实数c;或者对数组c;字符串进行原地修改的时候c;空间复杂度就是O(1)c;因为没有开辟新的空间
而如果是新建一个字符串c;数组就是需要新开辟一个数组或者字符串空间c;所以空间复杂度为O(n)
关于一些生活中常见的算法…
这里不讲代码c;只讲原理!
在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择c;从而希望导致结果是最好或最优的算法 。
他也叫贪心算法。
举个栗子:
你去超市买东西c;买了十三块钱的东西
贪婪算法就是:
先找你一张50的c;再找你一张20的c;再10的c;再5的c;再1的c;再1的
当然这也是一般收银员会选择的方法c;通过找给你最少张的纸币c;找给你所需要的钱
这就是贪婪算法
贪婪算法所能解决的问题的特性:
贪婪算法的有点事简单c;直观c;容易实现c;但是缺点也很明显c;那就是他会认为当前选择是满足条件的就进行下一个c;而不管当前操作是否会对下一操作产生影响。
- 分治法就是把一个复杂的问题分成两个或更多的相同或相似的子问题c;再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解c;原问题的解即子问题的解的合并。 - 说简单点就是:把一个复杂的问题分成几个简单的问题c;如果分的还不够简单c;那就接着分c;然后再把各个简单的问题解答c;最终的答案就是所有简单问题答案的并集
举个栗子:
给你一个有序数组和一个目标值c;请找出这个元素的下标
我们使用二分查找法
Java代码:
public class ErFen{ public static void @H_833_125@main(String[] a){ } public static int Defg(int[] nums, int target){ int start = 0; int end = 0; int mid = 0; for (int i=0;i<nums.lenrth;i++){ mid = (start+end)/2; if (nums[@H_329_109@mid]>target) end = mid; else start = mid+1; } return mid; } }
Python代码:
def Defg(nums:list, target:int)->int: start = 0 end = 0 mid = 0 for i in range(len(nums)): mid = (start + end) //2 if nums[@H_329_109@mid]>target: end = mid else: start = mid return mid
看不懂?没关系c;看这是什么!!!大宝贝!——LeetCode刷题278-简单-第一个错误版本
分治法所能解决的问题的特性:
整个问题可以分解为两个或者多个较小的问题
对每个子问题的求解类似于对整个问题的求解
如果子问题的规模或者难度仍旧很大c;那就继续使用分治法
分治法的难度较高c;技巧性较高c;需要使用者对问题有着透彻的理解c;效率也不高。
但是能解决很多复杂的问题。
在现实生活中c;有一类活动的过程c;由于它的特殊性c;可将过程分成若干个互相联系的阶段c;在它的每一阶段都需要作出决策c;从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定c;它依赖于当前面临的状态c;又影响以后的发展。当各个阶段决策确定后c;就组成一个决策序列c;因而也就确定了整个过程的一条活动路线.这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程c;这种问题称为多阶段决策问题。在多阶段决策问题中c;各个阶段采取的决策c;一般来说是与时间有关的c;决策依赖于当前状态c;又随即引起状态的转移c;一个决策序列就是在变化的状态中产生出来的c;故有“动态”的含义c;称这种解决多阶段决策最优化的过程为动态规划方法
这个算法是极其难以理解的c;就算理解c;代码也很难敲出来。
而也可以这么理解c;动态规划的塑像是与分治法的思想相反的c;如果说分治法这种吧一个问题分解成多个简单问题的方法叫做自上而下的方法c;那么动态规划就是一种自下而上的解决方法。
而动态规划也不会出现贪婪算法那种当前操作最优而不再以下一操作的情况。
举个栗子:
计算二项式Cnm的值
使用杨辉三角可以根据当前二项式生成更简单的二项式
而不会重复生成更简单的相同的二项式
所以才叫动态规划
动态规划解决的问题的特性:
有好多人都不会用c;包括某菜鸡博主~~
回溯法是一种优化的穷举法。 所谓穷举法就是穷举问题的所有可能性c;直到发现解决问题的最佳解为止。当然利用穷举法可以解决很大一部分的实际问题c;但由穷举法的实现过程可知它所花费的资源是相当多的。使用穷举法进行彻底的搜索彻底的比较c;要以大量的运算为基础c;而大量的运算势必要花费大量的时间c;有时这种消耗是计算机也承担不起的。所以用穷举法解决问题往往是不实际的。
说白了还是穷举法~~
举个栗子:
你站在一颗形状类似于一个思维导图的头结点
你想查看某个尾结点c;但是计算机可看不到c;所以使用回溯法
回溯法就是让你先沿着最左边的一直走
返回上一个父节点c;再往右走c;不是c;回到父节点的父节点
继续往右c;然后再往左…
循环往复c;直到找到你想要的尾结点才停止。
回溯法解决的问题的特性:
缺点:由于是穷举法c;所以效率极低
概率算法允许算法在执行过程中随机地选择下一个计算步骤。在很多情况下c;算法在执行过程中面临选择时c;随机性选择比最优选择省时c;因此概率算法可以在很大程度上降低算法的复杂度。
他也叫c;随机算法。
说直白了他就是碰运气c;但是总能碰到正确的答案c;但是得不到精准的答案。
只有在某些场合才会使得效率增大。
举个栗子:
比如说某国的总统选举
不让所有人进行投票选举
而是随机找一些人进行民意调查
最后统计结果
支持率搞得就是新的国家总统
效率是不是提高了!
你可以说结果是正确的c;但不能说结果是精准的
优点是在某种情况下能使得解决问题的效率大大提高c;缺点是不是所有的问题都适用。
希望阅读完我这篇文章c;能够让你对数据结构与算法打下基础。
兴趣是最好的老师c;坚持是不变的真理。 学习不要急躁c;一步一个脚印c;踏踏实实的往前走。 每天进步一点点c;日积月累之下c;再回头看看c;你@R_317_10585@自己已经变得很厉害了。
以上是大佬教程为你收集整理的【万字长文】不学算法你也应该知道的算法知识全部内容,希望文章能够帮你解决【万字长文】不学算法你也应该知道的算法知识所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。