## 时间复杂度与空间复杂度 > 参考： [算法时间复杂度求解法【详细过程说明】](https://www.cnblogs.com/fanchangfa/p/3868696.html) ### 定义 在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，基座T（n）=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进算法时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。 ### 大O推导法： 1. 用常数1取代运行时间中的所有加法常数 2. 在修改后的运行函数中，只保留最高阶项 3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数 --- ## 动态规划 > [算法-动态规划 Dynamic Programming--从菜鸟到老鸟](https://blog.csdn.net/u013309870/article/details/75193592) ### 什么情况下用动态规划 1. 求一个问题的最优解 2. 整体问题的最优解依赖于各个子问题的最优解 3. 问题之间有相互重叠的子问题 4. 从上往下分析问题，从下往上解决问题 ### 核心 **记住已经解决过的子问题的解** 记住求解的方法有两种： 1. 自顶向下的备忘录法 2. 自底向上 一般情况下使用递归会产生额外的开销，所以使用自底向上的动态规划方法要比备忘录方法好。 **先计算子问题，再由子问题计算父问题** ### 推导过程 1. 边界情况 2. 不符合子问题的一些情况，一般处于opt[1]、opt[2]等初始位置，单独赋值 3. 从后往前推演，可以得出状态转移方程 ## 深度搜索 ## 思路 深度优先遍历图的方法是，从图中某顶点v出发： 1. 访问顶点v； 2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问 3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。　 当然，当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫。事实上我们还有别的方法，那就是广度优先搜索(BFS). 一个树的深度搜索代码： ```cpp struct Node { int self; //数据 node *left; //左节点 node *right; //右节点 }; void DFS(){ const int TREE_SIZE = 9; std::stack<node*> visited, unvisited; node nodes[TREE_SIZE]; node* current; for( int i=0; i<TREE_SIZE; i++) //初始化树 { nodes[i].self = i; int child = i*2+1; if( child<TREE_SIZE ) //Left child nodes[i].left = &nodes[child]; else nodes[i].left = NULL; child++; if( child<TREE_SIZE ) //Right child nodes[i].right = &nodes[child]; else nodes[i].right = NULL; } unvisited.push(&nodes[0]); //先把0放入UNVISITED stack while(!unvisited.empty()) //只有UNVISITED不空 { current=(unvisited.top()); //当前应该访问的 unvisited.pop(); if(current->right!=NULL) unvisited.push(current->right); // 把右边压入 因为右边的访问次序是在左边之后 if(current->left!=NULL) unvisited.push(current->left); // 把左边压入 实现左边先于右边访问 visited.push(current); cout<<current->self<<endl; } } ``` --- ## 算法小技巧 + 在有限范围的输入时，可以将两个分离的变量编码，整合成一个变量。与Set结合这样十分有利于快速比较。见LeetCode874：WalkingRobotSimulation // 未完待续 <br /> <br /> <br /> <br /> <div align="right"> Chen Sicong 编写时间：2019年8月2日 20:30:22 </div>