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

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,自动管理内存
2	list,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搜索树