关键词：
1. 最大子序列和的问题
输入样例：4 -3 5 -2 -1 2 6 -2
输出：11
1.1 使用二分法递归求解代码如下(时间复杂度：O(NlogN))：GCC编译C++使用g++命令
int getMax3 (int a, int b, int c) { int max = a; if (max < b) max = b; if (max < c) max = c; return max; } int getMaxSum(const vector<int> &arr, int bgn, int end) { if (bgn >= end) return 0; int mid = (bgn + end) / 2; int leftMaxSum = getMaxSum(arr, bgn, mid); //此处的起始位置应设置为mid + 1，否则会造成无限递归 int rightMaxSum = getMaxSum(arr, mid + 1, end); int leftMaxBorder = 0, leftTmp = 0; for (int i = mid; i >= bgn; --i) { leftTmp += arr[i]; if (leftTmp > leftMaxBorder) leftMaxBorder = leftTmp; // if (leftTmp < 0) //这个地方不能提前退出，必须完全遍历 // break; } int rightMaxBorder = 0, rightTmp = 0; for (int i = mid + 1; i < end; ++i) { rightTmp += arr[i]; if (rightTmp > rightMaxBorder) rightMaxBorder = rightTmp; // if (rightTmp < 0) // break; } return getMax3(leftMaxSum, rightMaxSum, leftMaxBorder + rightMaxBorder); }
1.2 一次性遍历的求解方法如下(时间复杂度O(N))：
int getMaxSubSum(const vector<int> &arr, int bgn, int end) { int maxSum = 0; int sumTmp = 0; for (int i = bgn; i < end; ++i) { sumTmp += arr[i]; if (sumTmp > maxSum) maxSum = sumTmp; else if (sum < 0) sumTmp = 0; } return maxSum; }
2. 算法时间复杂度为O(logN)的典型问题：
2.1 对分查找（binary search）：时间复杂度（<= log2N）
int binSearch(const vector<int> &arr, int bgn, int end, int target) //end-尾元素后一位置 { int ret = -1; while (bgn < end) { int mid = (bgn + end) / 2; if (target == arr[mid]) { ret = mid; break; } else if (target > arr[mid]) bgn = mid + 1; else end = mid; } return ret; }
2.2 两个整数最大公约数求解（欧几里德算法）：时间复杂度（<= 2logN）
unsigned int getGCD(unsigned int m, unsigned int n) { while (n > 0) { int rem = m % n; m = n; n = rem; } return m; }
这里其实运用了递归的思想：m与n的最大公因子即是n与rem(m%n)的最大公因子...，那么，只需要说明n与rem的最大公因子就是m与n的最大公因子即可使这个递归进行下去。所以问题是n与rem的最大公因子为什么就是m与n的最大公因子？
思路：假设m > n，又即使m < n，经过一次遍历后有m > n，m与n的最大公因子是A，则m = xA, n = yA。
rem = m%n -> m-zn(z = m/n)，当rem=0，n即是两者的最大公因子；rem>0，rem=xA - zyA，很显然rem%A = 0
-> m与n的最大公因子即是n与rem的最大公因子，以此类推
2.3 幂运算：时间复杂度（<= 2logN）
long long pow(long long x, unsigned int n) { if (0 == n) return 1; if (n % 2) return pow( x*x, n/2 ) * x; else return pow( x*x, n/2 ); }
以2^15为输入，则恰需要 2log(15) = 6 次乘法运算
以2^16为输入，则仅需要 4+1(<2log(16)=8) 次乘法运算，也可以修改下代码添加出口判断（if (1 == n)）使之成为4次乘法运算，不过需要每次进入pow多判断一次
PS: 1. 书上以2^62为例，共需9次乘法运算，但所推演算法过程个人觉得有问题。实际过程应该是首先层层运算pow入口参数x*x的值，直至n == 0。
然后，再逆序层层计算pow*x的值，直至算法结束运算
2. 代码中语句pow( x*x, n/2 )可以用pow( x, n/2 )*pow( x, n/2 )代替，但是效率会非常低，因其进行了大量的重复性工作
数据结构与算法——1.1算法分析
什么是算法分析？比较方面：代码风格，可读性计算资源占用*空间（内存）占用*执行时间占用运行时间检测python中的time模块，当前时间，基准点----->1970年0点0时0分0秒不同运行环境（linuxorwindows？移动端or服务器？），编程语... 查看详情
《数据结构与算法分析》引论：选择问题实现
在《数据结构与算法分析——C语言描写叙述》的引论中有提到一个问题：设有一组N个数而要确定当中第k个最大者。被称为选择问题(selectionproblem)。后面有提到两种算法，以下是我依据描写叙述。写的代码：/**来源：《数据结构... 查看详情
数据结构与算法分析
书：《数据结构与算法分析：java语言描述》前四页时间：2017.9.417:03引论：主要复习了一些数学定理 指数、对数、级数、模运算 证明的方法： 归纳法：对直到某个有限数K的所有情况都是成立的，然后使用这个假设证... 查看详情
《数据结构与算法分析-第2章-算法分析》
2.1数学基础1.掌握O（N）的概念2.在需要大O表示的任何分析中，各种简化都是可能发生的，低阶项一般都会被自动忽略，常数也可以弃掉2.2模型1.对模拟机做的假设：1.模拟机做任何一件简单的工作（加法，减法，赋值，比较）都... 查看详情
数据结构与算法分析
数据结构：大量数据的组织方法；算法分析：算法运行时间的估算。涉及到计算效率。设想，如果能把时间限制从16年减至不到1秒，不很神奇吗？在很多问题中，一个重要的观念是：写出一个可以工作的程序并不够。如果这个程... 查看详情
数据结构与算法分析-排序
...lgorithm)是计算机算法的一个组成部分。也是程序=算法+数据结构中的一部分（算法）。实验平台：raspberry2B+UbuntuMate 插入排序外循环i由1到N-1，内循环由j由i到1，每次内循环都将A【j】插入到序列A【0】-A【i】的正 查看详情
数据结构与算法系列二（复杂度分析）(代码片段)
1.引子1.1.为什么要学习数据结构与算法？有人说，数据结构与算法，计算机网络，与操作系统都一样，脱离日常开发，除了面试这辈子可能都用不到呀！有人说，我是做业务开发的，只要熟练API，熟练框架，熟练各种中间件，写... 查看详情
数据结构与算法分析——分治法
#include<stdio.h>intbigger(inta,intb){return(a>b?a:b);}intmax(inta,intb,intc){returnbigger(a,bigger(b,c));}intmaxsubsequencesum(constintA[],intleft,intright){intmaxleftsum,maxrightsum;intmaxl 查看详情
python数据结构与算法（1.7）——算法分析(代码片段)
Python数据结构与算法（1.7）——算法分析0.学习目标1.算法的设计要求1.1算法评价的标准1.2算法选择的原则2.算法效率分析2.1大OOO表示法2.2常见算法复杂度2.3复杂度对比3.算法的存储空间需求分析4.Python内置数据结构性能分... 查看详情
跳跃表数据结构与算法分析
...地介绍跳跃表的由来以及各种常量的由来。作为一种概率数据结构，理解各种常量的由来可以更好地进行变化并应用到高性能功能开发中。本文没有重复地以对现有优秀实现进行代码分析，而是通过对跳跃表进行了系统性地介绍... 查看详情
数据结构与算法分析
1.最大子序列和的问题 输入样例：4-35-2-126-2 输出：11 1.1使用二分法递归求解代码如下(时间复杂度：O(NlogN))：GCC编译C++使用g++命令intgetMax3(inta,intb,intc){intmax=a;if(max<b)max=b;if(max<c)max=c;returnmax;}intgetMaxSum(constvector<in 查看详情
数据结构与算法分析-第1章
.titletext-align:center;margin-bottom:.2em.subtitletext-align:center;font-size:medium;font-weight:bold;margin-top:0.todofont-family:monospace;color:red.donefont-family:monospace;color:green.pr 查看详情
数据结构与算法分析-第3章
.titletext-align:center;margin-bottom:.2em.subtitletext-align:center;font-size:medium;font-weight:bold;margin-top:0.todofont-family:monospace;color:red.donefont-family:monospace;color:green.pr 查看详情
（数据结构与算法分析一）------快速求幂算法，java递归实现
...很简单，但是感觉非常经典，这个也是我开始看数据结构与算法分析这本书的开始把，大学期间感觉就得深究一下算法，课堂学习的太肤浅，只能自己干了，当然，也算是打基础吧，以后可能会更... 查看详情
python数据分析与挖掘学习笔记-电商网站数据分析及商品自动推荐实战与关联规则算法(代码片段)
这一节主要涉及到的数据挖掘算法是关联规则及Apriori算法。由此展开电商网站数据分析模型的构建和电商网站商品自动推荐的实现，并扩展到协同过滤算法。关联规则最有名的故事就是啤酒与尿布的故事，非常有效地说... 查看详情
20120920-avl树定义《数据结构与算法分析》
AVL树节点声明：1structAvlNode2{3Comparableelement;4AvlNode*left;5AvlNode*right;6intheight;78AvlNode(constComparable&theElement,AvlNode*lt,AvlNode*rt,inth=0):element(theElement),left(lt),right(rt),height 查看详情
《图解数据结构与算法》（java代码实现注释解析算法分析）(代码片段)
文章目录第1章数据结构与算法基础概述1.1数据结构和算法的重要性1.2数据结构概述逻辑结构存储结构1.3算法概述如何理解“大O记法”时间复杂度空间复杂度第2章数组2.1数组概念2.2无序数组2.3有序数组第三章栈3.1栈概念3.2栈的操... 查看详情
王道数据结构与算法之排序算法(代码片段)
这里是【王道计算机考研】数据结构与算法最终篇*★由于数据结构开篇较早，初始是按照【2021】年大纲来记录的笔记，并且中途结合了青岛大学王卓老师的课程来辅助理解，所以大家在浏览时会发现文章标题我已经... 查看详情