复杂度的分析

今日电面F，代码相对顺利写出。
但run test by hand以及复杂度分析陷入黑洞，在多次提示下算是给出答案。
所以，要好好总结
1，run test case by hand，在平时刷题时要加以练习。
要学会些main()，并且打印结果！！！//

一般就是写一个 main()，然后建一个链表，调用你写出的函数求出结果，打印，让面试官看到给出了正确答案。然后再自己想一些 corner case，让面试官了解你枚举常见 corner case 的能力。 2，复杂度分析。 （复杂度分析要跳出代码的执行细节，high level宏观的来看，元素被访问了几遍，一遍是O(N),在一遍里  嵌套着又一遍，是O(N)） 以今天的题目为例。 找所有从root到leaf的path， 时间复杂度，我开始给出的是O(2^N)，因为我想每个node都有左右两个节点。但其实忽略了N其实就是节点 的个数。 跳出来看，从high level看，binary tree里面的traverse 是每个点被遍历一次。所以，时间复杂度 是O(N)，而在每个节点上，都有for loop的操作。所以，还得乘以for loop里的遍历次数。for loop里次数是 leaf节点个数，leaf节点个数等于 2^height, 而height平均是log（n），所以leaf节点时O(N)。最终时间复杂度 是O(N^2). 这就是今天被面试官一步步引导的思维过程， 在面试时，一旦遇到需要现场推导的时候，别慌，一慌张，脑子就乱了，大脑充血。一步步去做。 不太可能，遇到的问题都是自己事先想到的。 空间复杂度，开始我提到了recursion调用函数产生的系统stack空间，但我心里也不清楚这方面的复杂度是多少。 感觉也没说清楚，就过去了。（对于recursion，系统stack的消耗是recursion的深度，也就是最大是几层 的recursion，也就是函数call自己再call自己的深度，对于DFS就是Deapth深度，具体tree是height，matrix是 max(m,n)。） 主要还是要看所用的定义的变量，也就是在系统heap memory上占用的空间。 leaf的个数 * height。所以是，O(N*logN). 开始我给出的是O(N)，就是leaf的个数，在面试官提示下，因为这是path，path的个数是N，但每个path的大小 是heigh，也就是logN。所以，思考复杂度，一定要记住这里的N是元素的个数。对于tree，graph，matrix就是 节点个数。 vector<string> binaryTreePaths(TreeNode * root) { // write your code here vector<string> res; if(root == NULL){ return res; } if(root->left == NULL && root->right == NULL){ res.push_back(to_string(root->val)); return res; } vector<string> left = binaryTreePaths(root->left); vector<string> right = binaryTreePaths(root->right); for(string l : left){ res.push_back(to_string(root->val) + "->" + l); } for(string r : right){ res.push_back(to_string(root->val) + "->" + r); } return res; }

对于DFS，还有recursion，他们的复杂度一直没有搞的太清楚，所以今天出现了黑洞。 再借此分析下 number of island  元素被访问了一遍，所以是O(m * n). DFS的最大深度是 max(m, n)，所以是系统stack memory space O(max(m, n)). heap是O(1)。 const int dir = 4; const vector<int> dx = {0, 0, -1, 1}; const vector<int> dy = {-1, 1, 0, 0}; int numIslands(vector<vector<bool>> &grid) { // write your code here const int m = grid.size(); if(m == 0){ return 0; } const int n = grid[0].size(); int res = 0; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(grid[i][j] == 1){ res++; dfs(i, j, grid); } } } return res; } void dfs(int i, int j, vector<vector<bool>> &grid){ //if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0){ // return; //} //grid[i][j] = 0; //for(int k = 0; k < dir; k++){ // dfs(i + dx[k], j + dy[k], grid); //} //return; //把条件放在里面 grid[i][j] = 0; for(int k = 0; k < dir; k++){ int newX = i + dx[k]; int newY = j + dy[k]; if(newX < 0 || newY < 0 || newX >= grid.size() || newY >= grid[0].size() || grid[newX][newY] == 0){ continue; } //grid[newX][newY] = 0; dfs(newX, newY, grid); } return; } 再分析下排列，组合，subset类的DFS解法复杂度，和graph，tree是不太一样。该类型的时间复杂度是就是所有可能性的个数，也就是结果的个数，因为要找到所有结果，就要遍历到。 所以时间复杂度 是O(2^N). 因recursion消耗的系统stack 空间复杂度是O(N),recursion的深度。 class Solution { public: /** * @param nums: the given array * @param s: the given target * @return: the number of ways to assign symbols to make sum of integers equal to target S */ int findTargetSumWays(vector<int> &nums, int s) { // Write your code here //完美的DFS类 combination类型，复杂度O(2^n), 每个元素有两种选择，- or +。 //所有可能的情况个数是 2^n. //和425. Letter Combinations of a Phone Number思路一样 const int size = nums.size(); if(size == 0){ return 0; } int cnt = 0; dfs(nums, s, 0, 0, cnt); return cnt; } void dfs(vector<int> &nums, int s, int idx, int sum, int &cnt){ if(idx == nums.size()){ if(sum == s){ cnt++; } return; } dfs(nums, s, idx + 1, sum + nums[idx], cnt); dfs(nums, s, idx + 1, sum - nums[idx], cnt); return; }

z再分析下排列组合subset类

这是permutation题目

结果个数是N！，所以时间复杂度是O(N!).

结果大小是N，总的结果空间复杂度是O(N*N!).

系统stack memory消耗O(N);

class Solution { public: /* * @param nums: A list of integers. * @return: A list of permutations. */ vector<vector<int>> permute(vector<int> &nums) { // write your code here const int size = nums.size(); vector<vector<int>> res; if(size == 0){ res.push_back(vector<int>()); return res; } vector<int> resElem; vector<int> visited(size, 0); dfs(nums, res, resElem, visited); return res; } void dfs(vector<int> &nums, vector<vector<int>> &res, vector<int> &resElem, vector<int> &visited){ if(resElem.size() == nums.size()){ res.push_back(resElem); return; } for(int i = 0; i < nums.size(); i++){ if(visited[i]){ continue; } resElem.push_back(nums[i]); visited[i] = 1; dfs(nums, res, resElem, visited); visited[i] = 0; resElem.pop_back(); } return; } };



subset类型的复杂度
有两种解法，但两种解法的复杂度为啥感觉不一样呢

第一种用了for循环，感觉复杂度是O(N!)
class Solution { public: /** * @param nums: A set of numbers * @return: A list of lists */ vector<vector<int>> subsets(vector<int> &nums) { // write your code here vector<vector<int>> res; vector<int> resElem; const int size = nums.size(); if(size == 0){ res.push_back(resElem); return res; } dfs(nums, res, resElem, 0); return res; } void dfs(vector<int> &nums, vector<vector<int>> &res, vector<int> &resElem, int start){ res.push_back(resElem); for(int i = start; i < nums.size(); i++){ // resElem.push_back(nums[i]); dfs(nums, res, resElem, i + 1); resElem.pop_back(); } return; } };

第二种是
复杂度是O(2^N)，因为有2^N种可能。代码实现也是2^N,可以解释，dfs内核是2，dfs深度是N，所以2^N.
感觉2^N是对的，但第一种方法看出来是2^N。奇怪
vector<vector<int>> subsets(vector<int> &nums) { // write your code here vector<vector<int>> res; vector<int> resElem; const int size = nums.size(); sort(nums.begin(), nums.end()); dfs(nums, res, resElem, 0); return res; } void dfs(vector<int> &nums, vector<vector<int>> &res, vector<int> &resElem, int start){ if(start == nums.size()){ res.push_back(resElem); return; } //for(int i = start; i < nums.size(); i++){ dfs(nums, res, resElem, start + 1); resElem.push_back(nums[start]); dfs(nums, res, resElem, start + 1); resElem.pop_back(); //} return; }

653. Expression Add Operators

vector<string> addOperators(string &num, int target) { // write your code here // 这是一道典型的DFS应用 // 拆分挡板放在哪里的问题。然后还加上中间选择的3个可能。 // 所以复杂度是4^N (不拆，放+，-，*，4个可能) vector<string> res; dfs(num, target, 0, "", res, 0, 0); return res; } void dfs(string &num, int target, int sum, string path, vector<string> &res, int start, int val){ if(start == num.size()){ if(sum == target){ res.push_back(path); } return; } for(int i = start; i < num.size(); i++){ // if(num[start] == '0'){ // substr only 0 if(path.size() == 0){ dfs(num, target, sum, path + "0", res, start + 1, 0); } else{ dfs(num, target, sum, path + "+0", res, start + 1, 0); dfs(num, target, sum, path + "-0", res, start + 1, 0); dfs(num, target, sum - val, path + "*0", res, start + 1, 0); // } break; } else{ string sub = num.substr(start, i - start + 1); long long subV = stoll(sub); if(path.size() == 0){ dfs(num, target, sum + subV, path + sub, res, i + 1, subV); } else{ dfs(num, target, sum + subV, path + "+" + sub, res, i + 1, subV); dfs(num, target, sum - subV, path + "-" + sub, res, i + 1, -subV); dfs(num, target, sum - val + val * subV, path + "*" + sub, res, i + 1, subV * val); } } } return; }