数据结构与算法Linux常用操作命令C++与Python

数据结构与算法Linux常用操作命令C++与Python,第1张

1.二叉树的前中后序遍历class="superseo">算法指的是:根节点的位置。

2.解决过拟合:正则化、增加数据集、Doupout、Early Stopping等等。

一、数据结构与算法 1.排序算法(十大经典排序算法)
复杂度为O(n^2)--抛("冒")开"选择","插入""希"望
冒泡排序交换相邻两个元素,像泡泡一样           
选择排序每次选择最小(或者最大,自定义)的放在前面
插入排序已选择+未选择
希尔排序插入排序+k趟排序    
复杂度O(nlogn)----"快""归"队("堆")
快速排序基准,比它大,比它小
归并排序分而治之
堆排序完全二叉树,根节点最大,移动到尾端
复杂度为O(n)----统("桶") "计" "基数"
桶排序0-9,10-19,20-29... 
计数排序分配内存,计数
基数排序个位+十位
2.基本算法思想(5类)

巧记:"贪分回枚动",即"贪"心准备"分"赃,"回"去发现钱却"枚"有解"动"。

贪心算法:每次选取在当前时刻最优的,并不一定能够得到最优解。

分治算法:分而治之,原问题划分为n个与原问题相似的子问题。

回溯算法:以深度优先方式系统搜索问题的解,适合用于解组合较大的问题。

枚举算法:将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适,保留合适的,舍弃不合适的。

动态规划:记住过去已经求过的解。Eg,斐波那契数列的求解以及求最大子序列。方法:自顶向下和自底向上。

# 斐波那契数列:线性规划代码
# 自顶向下(在执行的过程中将执行过的子节点保存起来,节省计算时间)、
def fib(n, Memo):
    if Memo[n] != -1:
        return Memo[n]
    if n <= 2:
        Memo[n] = 1
    else:
        Memo[n] = fib(n-1, Memo)+fib(n-1, Memo)
    return Memo[n]

def Fibonacci(n):
    if n <= 0:
        return n
    Memo = []
    for i in range(n+1):
        Memo.append(-1)
    return fib(n, Memo)

# 自底向上
def fib1(n):
    if n <= 0:
        return n
    Memo = [0]*(n+1)
    Memo[0] = 0
    Memo[1] = 1
    for i in range(2, n+1):
        Memo[i] = Memo[i-1]+Memo[i-2]
    return Memo[n]

def fib2(n):
    if n <= 0:
        return n
    Memo_i_2 = 0
    Memo_i_1 = 1
    Memo_i = 1
    for i in range(2,n+1):
        Memo_i = Memo_i_2 + Memo_i_1
        Memo_i_2 = Memo_i_1
        Memo_i_1 = Memo_i
    return Memo_i
3.搜索算法(3种)

(1)预备知识

  • 递归函数:一个函数自己调用自己的行为就叫递归。PS:调用时一定要有循环退出的条件,函数组成部分:循环退出条件 + 递归调用公式。

(2)深度优先搜索(Depth-First Search, DFS)

  • 它从某一个状态开始,不断地转移状态直到无法转移,然后回退到前一步的状态,继续转移到其他状态,如此不断重复,直到找到最终的解。隐式使用栈,相当于树的前序遍历。
  • Eg: 树结构,根节点出发  -->  ...  -->  叶子节点  -->  退回该叶子节点的父节点  --> 遍历该父节点的其他子节点  -->  ....  -->  直到遍历完所有节点
  • 关键之处在于找到深度遍历的条件(比如输入)。
"""
题目:给定n个整数,判断是否可以从中选出若干数,使得它们的和恰好等于k。
n: 4
: 1 2 4 7
k: 13
想法:DFS,分支条件为取和不取。
"""
# dfs函数的输入为当前所处的节点深度i和已经求得的sum。
def dfs(i, sum):
    if i == n:
        return sum == k
    # 左子树,选取arr[i]
    if dfs(i+1, sum+arr[i]):  
        return True
    # 右子树,不选取arr[i]
    if dfs(i+1, sum):          
        return True
    return False
dfs(0, 0)

(3)广度优先搜索(Breath-First Search, BFS)

  • 又称广度优先搜索,也是搜索算法的一种,它与深度优先搜索类似,从某个状态出发,搜索所有可到达的状态。隐式使用队列,相当于树的层次遍历。可以用来求最短路径和最少操作的问题。
  • Eg,树结构,根节点 -->  根节点对应的所有子节点 -->  取出首位子节点,在队列末端添加该子节点的所有子子节点 -->  取出下一位子节点 -->  ...(重复上述过程)--> 直到队列为空。
  • 关键之处在于事先定义一个与状态数成正比的内存空间和队列,然后定义x,y轴的上下左右搜索,最后设置判断是否被访问过以及如果被访问需要进行的操作。

(4)A*启发式搜索

  • 吸取Dijkstra 算法中的当前代价,为每个边长设置权值,不停的计算每个顶点到起始顶点的距离,以获得最短路线,同时也汲取贪婪最佳优先搜索算法中不断向目标前进优势,并持续计算每个顶点到目标顶点的距离,以引导搜索队列不断想目标逼近,从而搜索更少的顶点,保持寻路的最优解。
  • 选取综合优先级最高(值最小)的节点。
二、Linux操作系统部分命令

文件夹:ls(list查看当前文件下的内容)、cd(change diretory切换文件夹)、mkdir(make directory创建目录)、pwd(print work directory查看当前所在文件夹)-------4个

文件:touch(创建文件)、rm(remove删除指定文件)------2个

其他:clear(清屏)

查找文件:find[路径]-name.".py"

软连接:ln -s 被链接的源文件 链接文件(类似于Windows系统下的快捷方式)

软件安装:Advanced Packaging Tool

sudo apt install/remove/upgrade  安装/卸载/更新

三、C++和Python部分区别总结
名称C++Python
0面向对象的高级程序设计语言
1开发效率高,执行效率低。Eg,手动开辟和释放内存开发效率低,执行效率高。Eg,自动管理内存
2list,set,map,dequeue,stack,array,vector(7种)list,set,tuple,dictionary(4种)
3编译形语言,源程序经过预处理、编译、链接后生成可执行文件(二进制文件,可以直接与计算机底层打交道)解释型语言,P解释器先把源代码转换成字节码文件,再由Python虚拟机一条一条地执行字节码指令,和CPU之间多了 解释器这一层
4强类型语言,每个变量的类型都需要事先声明动态类型语言,变量不需要声明即可以直接赋值,对象的类型和内存都是在运行时确定的

解释1:C++在栈区无法定义指定大小的array,需要使用堆区另外指定内存(关键字new,字符*)。

  • 解释1_1: 栈区由编译器自动分配释放,存放函数的参数值、返回值和局部变量,在程序运行过程中实时分配和释放,栈区由操作系统自动管理,无须手动管理。
  • 解释1_2: 堆区是调用malloc函数来申请内存空间,这部分空间使用完后需要调用free()函数来释放。

以上内容是本人学习过程中的一些小笔记,参考了一些博主的内容,这里简要记录两个非常精彩和详细的参考文章。致谢!

(1) 排序算法细节参考:1.0 十大经典排序算法 | 菜鸟教程

(2) DFS和BFS参考:深度优先搜索(DFS)与广度优先搜索(BFS)详解_一棵快乐的二叉树的博客-CSDN博客_dfs搜索树

欢迎分享,转载请注明来源:内存溢出

原文地址:https://outofmemory.cn/langs/3002202.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-09-27
下一篇2022-09-27

随机推荐

发表评论

登录后才能评论

评论列表(0条)

    保存