/algorithum-learning

算法学习-Python,C++

Primary LanguageC++

实现语言Python,C++ #学习资料

第一章：基础知识

1.1时间复杂度和空间复杂度

（一）常见七种复杂度

  • O(1) : Constant Complexity
  • O(n) :Linear Complexity
  • O(n2) : N square Complexity
  • O(n3) : N cubic Complexity
  • O(2n) : Exponential Complexity
  • O(logn) : Logarithmic Complexity
  • O(n!) :Factorial

（二）支配定理
对于递归方法的复杂度分析，可使用master theorem定理来分析
参考：wiki百科-支配定理

（三）数据结构的操作复杂度

  • 普通链表：lookup的复杂度为O(n)，append、insert、delet为O（1）
  • 列表：insert、delete的复杂度为O(n),append、lookup为O（1）
  • 跳表：取代平衡树二分查找，多级索引进行加速查找，lookup复杂度降低为O(logn;但是维护成本高，空间换时间

（四）刻意训练方法

  • 5~10分钟思考，有思路可以实现，没有思路直接看题解
  • 看题解，背诵熟练（有的解法不好 可以不看）
  • 闭卷测试
  • 练习结果主要看时间，空间暂不考虑
  • 同一题要多练几遍！！！，看看网友的优秀方法

1.2树、二叉树、二叉搜索树

（1）二叉树遍历方式
树的循环比较麻烦，常用递归的方式
1.前序pre-order : 根-左-右
2.中序in-order : 左-根-右
3.后序post-order : 左-右-根

（2）二叉搜索树

  • 特征：左子树上所有节点均大于根节点的值；右子树上所有节点的值均大于根节点的树。
  • 搜索树的搜索时间复杂度为：O(logn)
  • 二叉搜索树demo .

第二章：基础排序

##2.0工具包utils.py

  • 函数计时器：function_timer(func)
使用Python修饰器实现
在定义的函数前面一行 插入一行 @function_timer
即可查看此函数运行时间
  • 随机数组生成器：generateRandomArray(length,rangeL,rangeR)
返回length长度，且在（rangeL,rangeR)范围内的整数数组
  • 检验排序是否正确：isSort(array) ##2.1 & 2.2选择排序
    基本思路：遍历列表中的值，搜寻该值以后所有值中的最小值，与之替换。
    时间复杂度：O（n2）
Python实现结构体：使用Class做定义，手动初始化和排序

##2.3插入排序 基本思路：遍历列表中的值，选中以后插入有序列表中的应有的位置，理论上通常比选择排序快一点，对于近乎有序的列表，速度提升会更明显，某些情况下速度会比一些O（n logn）算法更快。 时间复杂度：O（n2）
算法改进：实际操作时，发现插入排序反而比选择排序耗时。因为虽然判断的少，但是交换次数多，耗时反而比较长。 因此优化方法为：先把遍历位置的值取出保存，再与前一个比较大小，如果前一个大于当前值，则直接将前一个值后移。 如果小于则将缓存放在此处，减少交换产生的赋值次数。 值得注意的是，使用python内置的函数实现排序要比手动逐个实现要快得多。

算法：选择排序
程序运行：1.140265 s

算法：插入排序
程序运行：2.170480 s

算法：插入排序-改进1次后
程序运行：1.520350 s

算法：插入排序-改进3次后
程序运行：0.641137 s

##2.4希尔排序 基本思路：插入排序对于小规模或者基本有序的数组排序效率高，但是对于大规模无序数组则无优势。希尔排序通过把大规模无序数组分割成若干个小规模数组进行排列，实现对大规模无序数组同样拥有优势。

算法：优化后插入排序
程序运行：0.561127 s
算法：希尔排序
程序运行：0.021004 s

#第三章：高级排序 上一章的排序方法为常见基础排序，复杂度为O（n2）级别， 这一章介绍的排序方法复杂度级别为O（nlogn） ##3.1归并排序 基本思路:假设已经右两个已经排好序的子数组，并且和原来数组不在同一个存储空间。两个数组各有一个指针做追踪，还有一个最终生成位置的首部指针，依次移动，判断从哪个子数组中取出值存放进去。
##3.2快速排序 被誉为20实际最伟大的算法之一
基本思路：选中一个元素，想办法在数组中左边均小于他，右边均大于他（partition）。 问题：实际上如果排列近乎有序的列表，当规模大的时候，速度远远低于归并排序。
##3.2双路快速排序 程序运行：1.816214 s -快速排序
程序运行：1.807245 s -随机快速排序
程序运行：0.045031 s -双路快排
基本思路：随机选取一个值放在最左边，左边从l+1开始，右边从r开始遍历，保证i左边j右边分别为小于v和大于v的值。
直到i,j均指到不满足条件的值，这时候再调换i,j中的值继续运行。
优点：对于键值少，重复多的排序更快。
##3.3三路快速排序
基本思路：三路快排是在双路的基础上，多分了个等于v的部分。因此，原来的p分为两部分，变成了lt、gt分为三部分。
区别：三路快排对于重复值多的排序比双路快排快，但是对于重复少的反而不如双路快排。

#第四章：堆
先验知识：

  • 普通队列：先进先出，后进后出
  • 优先队列：出队顺序和入队顺序无关，和优先级有关
  • 优先队列的特色，例如在N个元素中寻找前M个元素，如果用高级排序大概是NlogN复杂度，但是通过优先队列，可以降维NlogM复杂度。
入队 出队
普通数组 O（1） O(n)
顺序数组 O(n) O(1)
堆 O（lgn） O（lgn）
  • 二叉堆：Binary Heap，子节点不大于父节点。而且是完全二叉树，即有限满足最左面的子节点。
  • 二叉堆的性质：
    ①i节点的parent节点为i/2
    ②i节点的左子节点为2i
    ③i节点的右子节点为2    i+1