算法复杂度

本文首发自「慕课网」，想理解更多IT干货内容，程序员圈内热闻，欢送关注"慕课网"！作者：s09g|慕课网讲师 咱们晓得面对同一道问题可能有多种解决方案。天然地，咱们会将多种办法进行比拟。那么怎么样能力晓得是A办法好，还是B办法好？这时候咱们就须要对算法的复杂度进行剖析。本章咱们先介绍两个概念：工夫复杂度与空间复杂度。并且用Two Sum作为案例，用工夫空间复杂度剖析Two Sum的三种解法。 工夫复杂度工夫复杂度形容的是算法执行须要耗费的工夫。同等条件下，耗费工夫越少，算法性能越好。然而，算法执行的确切工夫无奈间接测量，通常只有在理论运行时能力晓得。所以咱们通过估算算法代码的办法来失去算法的工夫复杂度。空间复杂度空间复杂度形容的是算法在执行过程中所耗费的存储空间（内存+外存）。同等条件下，耗费空间资源越少，算法性能越好。大O符号大O符号是用于形容函数渐近行为的数学符号，在剖析算法效率的时候十分有用。借用wikipedia上的一个例子，解决一个规模为n的问题所破费的工夫能够示意为：T(n)=4n2+2n+1。当n增大时，n2项将开始占主导地位，而其余各项能够被疏忽。比方当n=500，4n2项是2n项的1000倍大，因而在大多数场合下，省略后者对表达式的值的影响将是能够忽略不计的。久远来看，如果咱们与任一其余级的表达式比拟，n2项的系数也是无关紧要的。例如：一个蕴含n2项的表达式，即便T(n)=1,000,000n2，假设U(n)=n3，一旦n增长到大于1,000,000，后者就会始终超过前者。案例：Two Sum 给出一个整数数组nums和一个target整数，返回两个和为target的整数。假设咱们正在面试，让咱们用面试的办法来剖析一下这道题。1.向面试官确认输出、输入通过询问面试官，咱们能够晓得：输出是一个int类型的数组和一个target；返回值是两个下标，并且以数组的模式返回；办法名没有特殊要求。这样一下咱们就确定了函数的签名 public int[] twoSum(int[] nums, int target) { // Solution}2.向面试官确认输出、输入是否有特例接下来咱们要确认一下输入输出的细节 输出是否能够为空？输出的数组范畴是正整数，还是任意范畴？输出数组会不会特地大，甚至无奈载入内存，比方300GB的数据量？如果输出不非法或者没有正确答案，咱们曾经返回空数组还是抛出异样？输出的数组中有反复么？如果没有反复，能够同一个数字用两次么？如果有多个解，那么返回第一个，还是所有解？你心愿答案写成class，还是只提供办法自身即可？……有些问题即便题目中曾经提到，最好还是再次向面试官确认。如果以上这些问题你没有想到的话，那么阐明思路仅限于做题，不足面试的沟通技巧。能够多找小伙伴Mock面试，留神多交换。假如面试官通知咱们：只须要写函数自身。输出数组可能为空，但不会大到无奈读进内存。数字的范畴就是int类型的范畴，可能有反复。对于不非法或者没有正确答案的状况，请自行判断。多个解法是，返回任意一个答案都能够。失去了这些信息，咱们能够先进行防御性编程。 public int[] twoSum(int[] nums, int target) { if (nums == null || nums.length < 2) { return new int[0]; } // TODO: solution here return new int[0];}3.举几个例子接下来，咱们能够要求面试官举几个例子，或者本人提出几个例子，来确保单方对题目没有异议。 Example 1:Input: nums = [], target = 0Output: []Example 2:Input: nums = [2], target = 4Output: []Example 3:Input: nums = [2, 3, 4, 2], target = 6Output: [2, 4] or [4, 2]Example 4:Input: nums = [2, 7, 11, -2], target = 9Output: [2, 7] or [7, 2] or [11, -2] or [-2, 11]依据例子1、2，确定没有正确解时返回空数组。依据例子2，确定数字不可重复使用。依据例子3、4，确定如果有多个适合的解，返回任意一个都能够。 ...

1031. 两个非重叠子数组的最大和关键词：前缀和题目起源：1031. 两个非重叠子数组的最大和 - 力扣（Leetcode） 题目形容 T前缀和给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠 子数组 中元素的最大和，长度别离为 firstLen 和 secondLen 。 长度为 firstLen 的子数组能够呈现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。 子数组是数组的一个 间断 局部。 输出：nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2输入：20解释：子数组的一种抉择中，[9] 长度为 1，[6,5] 长度为 2。输出：nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2输入：29解释：子数组的一种抉择中，[3,8,1] 长度为 3，[8,9] 长度为 2。输出：nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3输入：31解释：子数组的一种抉择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。数据范畴1 <= firstLen, secondLen <= 10002 <= firstLen + secondLen <= 1000firstLen + secondLen <= nums.length <= 10000 <= nums[i] <= 1000问题剖析两个不重叠子数组必然位于某条分界线的两侧，于是，无妨枚举每条分界线，设其左侧子数组的最大值为l，右侧子数组的最大值为r，则，max{ l+r }即为答案。 ...

1. 背景可能很多同学都不知道，从打开美团App点一份外卖开始，然后在半小时内就可以从骑手小哥手中拿到温热的饭菜，这中间涉及的环节有多么复杂。而美团配送技术团队的核心任务，就是将每天来自祖国各地的数千万份订单，迅速调度几十万骑手小哥按照最优路线，并以最快的速度送到大家手中。 在这种场景下，骑手的交付时间，即骑手到达用户附近下车后多久能送到用户手中，就是一个非常重要的环节。下图是一个订单在整个配送链路的时间构成，时间轴最右部分描述了交付环节在整个配送环节中的位置。交付时间衡量的是骑手送餐时的交付难度，包括从骑手到达用户楼宇附近，到将餐品交付到用户手中的整个时间。 交付时间的衡量是非常有挑战的一件事，因为骑手在送餐交付到用户手中时会碰到不同的问题，例如：骑手一次送餐给楼宇内多个用户，骑手对于特定楼宇寻址特别困难，骑手在交付楼宇附近只能步行，老旧小区没有电梯，写字楼无法上楼，或者难以等到电梯等等。交付时间预估需要具备刻画交付难度的能力，在定价、调度等多个场景中被广泛使用。例如根据交付难度来确定是否调节骑手邮资，根据交付难度来确定是否调节配送运单的顺序，从而避免超时等等。总的来说，交付时间预估是配送业务基础服务的重要一环。 但是，交付时间预估存在如下的困难： 输入信息较少，且多为非数值型数据，目前能够被用来预估的仅有如下维度特征：交付地址、交付点的经纬度、区域、城市，适配常规机器学习模型需要重新整理且容易丢失信息。计算性能要求很高。由于是基础服务，会被大量的服务调用，需要性能TP99保证在10ms以内，整个算法平均响应时间需要控制在5ms内，其中包括数据处理及RPC的时间。且该标准为CPU环境下的性能要求，而非GPU下的性能要求。 总结起来，交付时间预估的问题，在于需要使用轻量级的解决方案来处理多种数据形式的非数值型数据，并提取有效信息量，得到相对准确的结果。在相同效果的前提下，我们更倾向于性能更优的方案。 在本文中，我们介绍了交付时间预估迭代的三个版本，分别为基于地址结构的树模型、向量召回方案以及轻量级的End-to-End的深度学习网络。同时介绍了如何在性能和指标之间取舍，以及模型策略迭代的中间历程，希望能给从事相关工作的同学们有所启发和帮助。 2. 技术迭代路径首先，在交付时间预估的技术迭代上，我们主要经历了三个大版本的改动，每一版本在5ms计算性能的约束下，追求轻量化的解决方案，在兼顾提升效果的基础上，不显著增加性能的消耗。 本章节分别叙述了3个模型的迭代路径，包括技术选型、关键方案及最终效果。 2.1 树模型技术选型 最早也是最容易被考虑到的是利用规则，核心思路是利用树结构衡量地址相似性，尽可能在相似的交付地址上积聚结构化数据，然后利用局部的回归策略，得到相对充裕的回归逻辑，而未能达到回归策略要求的则走兜底的策略。 为了快速聚积局部数据，树模型是一个较为合适的解决方案，树的规则解析能够有效地聚集数据，同时一个层级并不深的树，在计算速度上，具备足够的优势，能够在较短的时间内，得到相对不错的解决方案。 观察用户填写地址以及联系实际中地址的层级结构，不难发现，一个地址可以由四级结构组成：地址主干词（addr）、楼宇号（building）、单元号（unit）、楼层（floor）。其中的地址主干词在实际中可能对应于小区名或者学校名等地标名称。例如望京花园1号楼2单元5楼，解析为（望京花园，1号楼，2单元，5楼）。通过分析，实际交付时长与楼层高低呈正相关关系，且不同交付地址的交付时长随楼层增加的变化幅度也有所区别，所以可以使用线性回归模型拟合楼层信息和交付时长的关系，而地址主干词、楼宇号、单元号作为其层级索引。但用户填写的地址中并不一定包含完整的四级结构，就会存在一定比例的缺失，所以利用这样的层级结构构建成一棵树，然后充分利用上一层已知的信息进行预估。预测时，只需根据结点的分支找到对应的模型即可，如果缺失，使用上一层结构进行预测。对于没有达到训练模型要求数据量的地址，使用其所在的区域平均交付时长作为交付时长的预估结果，这部分也可以看作区域信息，作为树结构的根节点。 迭代路径 整体的思路是基于离散特征训练树模型，在树的结点上基于楼层训练线性回归模型。树结点训练分裂规则：（1）数据量大于阈值；（2）分裂后MAE（平均绝对误差）的和小于分裂前。考虑到数据的时效性，采用加权线性回归增加近期数据的权重。 2.2 树模型+向量召回方案技术选型 向量召回作为主流的召回方案之一，被业界广泛使用，在使用LSH、PQ乘积量化等常用开源工具基础上，高维向量召回性能通常在毫秒量级。 而从算法上考虑，树模型中NLP地址解析结果能够达到模型使用要求的仅为70%+，剩余20%+的地址无法通过训练得到的模型从而只能走降级策略。利用高维向量来表达语义相似性，即利用向量来表达地址相似性，从而用相似数据对应的模型来替代相似但未被召回数据，将地址主干词进行Embedding后，摆脱主干词完全匹配的低鲁棒性。 例如，在地址上可能会出现【7天酒店晋阳街店】数据量比较充足，但【7天连锁酒店太原高新区晋阳街店】数据量不充足从而无法训练模型的案例，这可能是同一个交付位置。我们希望尽可能扩大地址解析的成功率。 迭代路径 整个技术路径较为清晰简单，即利用Word2Vec将charLevel字符进行Embedding，获得该地址的向量表示，并且融入GPS位置信息，设计相应兜底策略。 最终效果 比较大地提升了整体策略的召回率，提升了12.20pp，对于未被上一版本树模型召回的地址，指标有了显著的提升，其中ME下降87.14s，MAE下降38.13s，1min绝对偏差率减小14.01pp，2min绝对偏差率减小18.45pp，3min绝对偏差率减小15.90pp。 2.3 End-to-End轻量化深度学习方案技术选型 在树模型的基础上，迭代到向量召回方案，整个模型的召回率有了较大幅度的增长，但仍然不是100%。分析发现，召回率提升的障碍在于NLP对于地址解析的覆盖率。 整个方案的出发点： 从模型复杂度考虑，同样仅仅使用地址信息的话，在提升模型VC维的基础上，使用其他的模型方案至少可以持平树模型的效果，如果在这基础上还能融入其他信息，那么对于原模型的基线，还能有进一步的提升。 考虑到不仅仅需要使用地址数据，同时需要使用GPS数据、大量ID类的Embedding，对于各类非数值类型的处理灵活性考虑，采用深度学习的方案，来保证多源且多类型特征能在同一个优化体系下优化学习。 工程上需要考虑的点： 交付模型作为基础模型，被广泛应用在路径构造、定价、ETA等各个业务中频繁调用，在树模型版本中，对于性能的要求为平均响应时间5ms，TP99在10ms左右，本方案需要考虑沿袭原业务的性能，不能显著增加计算耗时。 交付模型的难点在于非数值型特征多，信息获取形式的多样化，当前的瓶颈并不在于模型的复杂度低。如果可以轻量地获取信息及融合，没必要对Fusion后的信息做较重的处理方案。 所以整体的设计思路为：利用深度学习融合非数值型特征，在简单Fusion的基础上，直接得到输出结构，对于组件的选择，尽可能选用Flops较低的设计。该设计背后意图是，在充分使用原始输入信息，在尽可能避免信息损失的基础上，将非数值型的信息融入进去。并将信息充分融合，直接对接所需要的目标。而选用的融合组件结构尽可能保证高性能，且具备较高学习效率。这里分别针对地址选用了较为Robust的LSTM，针对GPS选用了自定义的双线性Embedding，兼顾性能和效果。 迭代路径 开始采用端到端的深度学习模型，这里首先需要解决的是覆盖率问题，直接采用LSTM读取charLevel的地址数据，经过全连接层直接输出交付时间。作为第一版本的数据，该版本数据基本持平树模型效果，但对于树模型未召回的20%数据，有了较大的提升。 在采用charLevel的地址奏效后，我们开始采用加入用户地址GPS的信息，由于GPS为经纬度信息，非数值型数据，我们使用一种基于地理位置格点的双线性插值方法进行Embedding。该方案具备一定的扩展性，对不同的GPS均能合理得到Embedding向量，同时具备平滑特性，对于多对偏移较小的GPS点能够很好的进行支持。 最终方案将地址Embedding后，以及GPS点的Embedding化后，加入下单时间、城市ID、区域ID等特征后，再进行特征融合及变换，得到交付模型的时间预估输出。整个模型是一个端到端的训练，所有参数均为Trainable。 扩展组件 在证实End-to-End路径可行后，我们开始进行扩展组件建设，包括自定义损失函数、数据采样修正、全国模型统一等操作，得到一系列正向效果，并开发上线。 特征重要性分析 对于深度学习模型，我们有一系列特征重要性评估方案，这里采用依次进行Feature Permutation的方式，作为评估模型特征重要性的方式。 考虑GPS经纬度和用户地址存在较大程度的信息重叠，评估结果如下。Shuffle后，用户地址的特征重要性高于GPS经纬度的特征重要性。加入GPS后ME下降不如地址信息明显，主要是地址信息包含一定冗余信息（下文会分析），而其他信息的影响则可以忽略不计。 特征特征重要排名用户地址1GPS经纬度2其他特征......注：在配送的其他案例中，商户GPS的经纬度重要性>>用户地址重要性>>用户GPS的经纬度重要性，该特征重要性仅仅为本案例特征重要性排序，不同学习目标下可能会有比较明显差别。 最终效果 End-to-End深度学习模型的最终效果较为显著：对于树模型及向量召回方案的最痛点，覆盖率得到彻底解决，覆盖率提升到100%。ME下降4.96s，MAE下降8.17s，1min绝对偏差率减小2.38pp，2min绝对偏差率减小5.08pp，3min绝对偏差率减小3.46pp。同时，对于之前树模型及向量召回方案未能覆盖到的运单，提升则更为明显。 3. 模型相关分析在整个技术迭代的过程中，由于整个解决方案对于性能有着较为苛刻的要求，需要单独对方案性能进行分析。本章节对向量召回方案及深度学习方案进行了相应的性能分析，以便在线下确认性能指标，最终保证上线后性能均达到要求。下文分别着重介绍了向量匹配的工具Faiss以及TensorFlow Operation算子的选取，还有对于整体性能的影响。 同时对比End-to-End生成向量与Word2Vec生成向量的质量区别，对于相关项目具备一定的借鉴意义。 3.1 向量召回性能最近邻搜索（Nearest Neighbor Search）指的是在高维度空间内找到与查询点最近点的问题。在数据样本小的时候，通过线性搜索就能满足需求，但随着数据量的增加，如达到上百万、上亿点时候，倾向于将数据结构化表示来更加精确地表达向量信息。 此时近似最近邻搜索ANN（Approximate Nearest Neighbor）是一个可参考的技术，它能在近似召回一部分之后，再进行线性搜索，平衡效率和精度。目前大体上有以下3类主流方法：基于树的方法，如K-D树等；基于哈希的方法，例如LSH；基于矢量量化的方法，例如PQ乘积量化。在工业检索系统中，乘积量化是使用较多的一种索引方法。 针对向量召回的工具，存在大量的开源实现，在技术选型的过程中，我们参照ANN-Benchmarks以及Erikbern/ANN-Benchmarks中的性能评测结果。在众多ANN相关的工具包内，考虑到性能、内存、召回精度等因素，同时可以支持GPU，在向量召回方案的测试中，选择以Faiss作为Benchmark。 ...

[TOC] 这里主要是算法的介绍以及一些判断算法好坏的标准和方式 引入如果a+b+c = 1000,且a^2 + b^2 = c^2,如何求出所有a,b,c可能的组合？ 第一次尝试:import timeprint("开始")start_time = time.time()for a in range(1001): for b in range(1001): for c in range(1001): if a + b + c==1000 and a ** 2+b ** 2 == c ** 2: print("a,b,c:%d,%d,%d" % (a, b, c))end_time = time.time()print("time:{}".format(end_time - start_time))print("结束")# 时间复杂度：Ｔ(n) = n^3 *2开始a,b,c:0,500,500a,b,c:200,375,425a,b,c:375,200,425a,b,c:500,0,500time:140.17622900009155结束算法算法的概述算法是独立存在的一种解决问题的方法和思想 算法的五大特性：输入： 0个或多个输入输出： 1个或多个输出有穷性： 有限步骤，可接受时间范围内完成确定性： 每一步具有确定的意义，不会出翔二义性可行性： 能不能实现第二次尝试：提示：c=1000-a-b import timeprint("开始")start_time = time.time()for a in range(1001): for b in range(1001): c = 1000 - a - b if a ** 2+b ** 2 == c ** 2: print("a,b,c:%d,%d,%d" % (a, b, c))end_time = time.time()print("time:{}".format(end_time - start_time))print("结束")# 时间复杂度：Ｔ(n) = n^2 *3开始a,b,c:0,500,500a,b,c:200,375,425a,b,c:375,200,425a,b,c:500,0,500time:1.0204615592956543结束解决一个问题有多个算法，每个算法的效率还是有差距的,如何判断算法的效率呢？ ...

关注公众号「前端小苑」，阅读 时间复杂度详解全文。 通过学习本文，你可以掌握以下三点内容： 为什么需要时间复杂度时间复杂度怎么表示怎样分析一段代码的时间复杂度相信认真阅读过本文，面对一些常见的算法复杂度分析，一定会游刃有余，轻松搞定。文章中举的例子，也尽量去贴近常见场景，难度递增。 复杂度是用来衡量代码执行效率的指标，直白讲代码的执行效率就是一段代码执行所需要的时间。 那么，有人会问了，代码执行所需要的时间，我执行一下，看看用了多少时间不就可以了？还要时间复杂度干啥？ 一、为什么需要时间复杂度实际开发时，我们希望自己的代码是最优的，但总不能把所有的实现的方式都写出来，再跑一遍代码做比较，这样不太实际，所以需要一个指标可以衡量算法的效率。而且，直接跑代码看执行时间会有一些局限性： 1.测试结果受当前运行环境影响同样的代码在不同硬件的机器上进行测试，得到的测试结果明显会不同。有时候同样是a,b两段代码，在x设备上，a执行的速度比b快，但到了y设备上，可能会完全相反的结果。 2.测试结果受测试数据的影响不同的测试数据可能会带来不同的结果，比如我们采用顺序查找的方法查找数组中的一个元素，如果这个元素刚好在数组的第一位，执行一次代码就能找到，而如果要找的元素位于数组最后，就要遍历完整个数组才能得到结果。 于是乎，我们需要一个不受硬件，宿主环境和数据集影响的指标来衡量算法的执行效率，它就是算法的复杂度分析。 二、时间复杂度怎么表示我们知道了为什么需要时间复杂度，那要怎么来表示它呢？下面通过一个简单例子，来说明一下 大O时间复杂度表示法。 首先看第一个例子： function factorial(){ let i = 0 // 执行了1次 let re = 1 // 执行了1次 for(;i < n; i++ ){ // 执行了n次 re*= n // 执行了n次 } return re // 执行了1次}上面代码是求n的阶乘（n!）的方法，即n×...×3×2×1 我们粗略的计算一下这段代码的执行时间。 首先，为了方便计算，假设执行每行代码的执行时间是相同的。 在这里，假设每行代码执行一次的时间设为t，代码的总执行时间为T(n)。 代码的第2行,第3行执行了一次，需要的时间是t ＋ t ＝ 2t; 代码的第4行，第5行都执行了n次，所以用时(n ＋ n)t ＝ 2n*t; 代码的第7行，只执行了一次，需要时间 t。 所以执行这段代码的总时间是： T(n) = 2t + 2nt + t = (2n ＋ 3)t我们以n为x轴，T(n)为y轴，绘制出坐标图如下： ...

网址：https://algorithm-visualizer….进去之后的页面是程序员熟悉的码农风格：假设我想学习冒泡排序算法，在搜索栏里输入sort，在结果列表里选择bubble sort：点击之后，排序操作处于就绪状态，点击play开始：此时右边的JavaScript代码像我们平时单步调试一样逐行执行，同时每一步执行后排序的效果在屏幕正中实时显示：比单步调试更强大之处是，我们能随时回退到前面的执行结果，通过下图高亮的84/144这个柱状开关控制。144意思是这个排序全过程总共要进行144次单步执行，当前已经执行了84步。自动播放的速度也可以在下图所示的Speed开关控制。这是非波拉契数列的生成动画：二叉树的遍历动画：Dijkstra迪杰斯特拉算法最短路径算法：有了这个网站，算法学习从此不再枯燥。这个网站的源代码是完全开源的，如果你有新的算法想给全世界的编程爱好者展示，可以按照Readme.md里定义的规范，提交您的动画。https://github.com/algorithm-…截至2019年3月16日，已经有14000多个赞了，顺手去点一个吧。要获取更多Jerry的原创文章，请关注公众号"汪子熙":

前言在算法性能上我们常常面临的挑战是我们的程序能否求解实际中的大型输入：–为什么程序运行的慢?–为什么程序耗尽了内存?没有理解算法的性能特征会导致客户端的性能很差，为了避免这种情况的出线，需要具备算法分析的一些知识。此篇主要涉及一些基础数学知识和科学方法，以及如何在实践应用中使用这些方法理解算法的性能。我们的重点放在获得性能的预测上。主要分为5部分：观察特点 (observations)数学模型 (mathematical models)增长阶数分类 (order-of-growth classifications)算法理论 (theory of algorithms)内存使用 (memory)我们将从多种不同的角色思考这些问题：程序员：解决一个问题，让算法能够工作，并部署它用户：完成某项工作，但不关心程序做了什么理论家：想要理解发生的事情团队：可能需要完成以上角色的所有工作关于算法分析需要集中考虑的关键是运行时间。运行时间也可以理解为完成一项计算我们需要进行多少次操作。这里主要关心：预测算法的性能比较完成同一任务不同算法的性能在最坏情况下算法性能的底线理解算法如何运行的一些理论基础算法分析的科学方法概述：从自然界中观察某些特征(程序在计算机上的运行时间)提出假设模型(与观察到的现象相一致的模型)预测(利用上边的假设做出合理的预测，一般用来预测更大问题规模，或者另一台计算机上的运行时间)验证(作更多的观察来验证我们的预测)证实(重复地验证直到证实我们的模型和观察的特征吻合，证实我们的模型假设是正确的)使用科学方法有一些基本原则：别人做同样的实验也会得到相同的结果假设必须具备某个特殊性质：可证伪性(可证伪性：指从一个理论推导出来的结论（解释、预见）在逻辑上或原则上要有与一个或一组观察陈述与之发生冲突或抵触的可能。可证伪，不等于已经被证伪;可证伪，不等于是错的。)观察第一步是要观察算法的性能特点，这里就是要观察程序的运行时间。给程序计时的方法：看表(你没看错，简单粗暴)利用API：很多第三方或者Java标准库中有一个秒表类，可以计算用掉的时间(如apache commons lang,springframework的工具包都有，这里使用stdlib库中的Stopwatch API 进行时间监控)我们将使用 3-SUM 问题作为观察的例子。3-SUM问题描述三数之和。如果有N个不同的整数，以3个整数划为一组，有多少组整数只和为0.如下图，8ints.txt 有8个整数，有四组整数和为0目标是编写一个程序，能对任意输入计算出3-SUM整数和为0有多少组。这个程序实现的算法也很简单，首先是第一种，“暴力算法”“暴力算法"EN：brute-force algorithm这里使用第三方API的方法测量程序运行的时间。import edu.princeton.cs.algs4.StdIn;import edu.princeton.cs.algs4.StdOut;import edu.princeton.cs.algs4.Stopwatch; public class ThreeSum { public static int count(int[] a) { int N = a.length; int count = 0; //三重的for循环，检查每三个整数组合 for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) for (int k = j + 1; k < N; k++) //为了方便观察算法的性能问题，这里忽略了整型溢出问题的处理 if (a[i] + a[j] + a[k] == 0) count++; return count; } /** * 读入所有整数，输出count的值 * 利用StopWatch执行时间监控 * @param args / public static void main(String[] args) { int[] a = StdIn.readAllInts(); Stopwatch stopwatch = new Stopwatch(); StdOut.println(ThreeSum.count(a)); double time = stopwatch.elapsedTime(); } }实证分析测试数据可以用越来越大的输入来运行。每次将输入的大小翻倍，程序会运行得更久。通过类似的测试，有时能相当方便和快速地评估程序什么时候结束。数据分析通过实证得出的数据，可以建立图像，使观察跟直观：标准坐标 ：Y轴：运行时间；X轴：输入大小双对数坐标：Y轴：取运行时间的对数；X轴：取问题输入大小的对数(lg以2为底)使用双对数坐标通常情况下是得到一条直线，这条直线的斜率就是问题的关键。这个例子(3-SUM 暴力算法)的斜率是3–通过对数坐标的方法得出公式：lg(T(N)) = blgN + c (可看做 y = bx + c，其中 y = lg(T(N))，x = lgN)–通过图中两点可求出b,c值，如果等式两边同时取2的幂，就得到 T(N) = 2cN^b, 其中 2c 为一个常数，可记作 a由此，从这个模型的观察中我们就得到了程序的运行时间，通过一些数学计算(在这里是回归运算)，我们就知道得出了运行时间：T(N) = aN^b (b为双对数坐标中直线的斜率，同时 b 也是这个算法的增长量级，第三点会讲到)预测和验证假设通过上述的数据分析，我们得出假设：运行时间看起来大约是 1.006 × 10^–10 × N^2.999 (秒)预测可以运用这个假设继续做预测，只要带入不同的N值，就能计算出需要的大致时间。・51.0 seconds for N = 8,000.・408.1 seconds for N = 16,000.验证通过对比 程序实际运行时间(下图) 和 通过我们的假设模型预测的时间上一步) 可以看出结果非常相近这个模型帮助我们在不需要花时间运行试验的前提下做一些预测。实际上这个情形中存在幂定律(aN^b).实际上绝大多数的计算机算法的运行时间满足幂定律。下边介绍一种求解符合幂定律运行时间中的增长量级值(b)的方法Doubling hypothesis 方法计算b值这里可以通过 Doubling hypothesis 的方法可以快速地估算出幂定律关系中的 b 值：运行程序，将每次输入的大小翻倍(doubling size of the input)，然后计算出N和2N运行时间的比率。主要看下图的后几行运算时间比率，前几行的输入值小，以现在的计算机运算能力处理起来，立方级别的增量级运算速度快也相差无几。ratio ≈ T(2N)/T(N).至于为什么 0.8/0.1≈7.7 或其他看起来 “运算错误” 类似的情况，是因为图上的运行时间的记录是简化精确到了小数点后一位，实际运算比率值是使用了实际运行时间(精确到小数点后几位)去计算的，所以会出现0.8/0.1≈7.7。通过不断地进行双倍输入实验，可以看到比率会收敛到一个常数(这里为8)，而实际上比率的对数会收敛到N的指数，也就是 b 的值，这里粗暴算法的 b 值就等于3通过Doubling hypothesis方法我们又能提出假设：此算法的运行时间大约是 aN^b, 其中 b = lg ratio注意：Doubling hypothesis 不适用于识别对数因子计算a值得出 b 的值后，在某个大的输入值上运行程序，就能求出 a 值。由此得出假设：运行时间 ≈ 0.998 × 10^–10 × N^3 (秒)我们通过作图得出的模型( ≈ 1.006 × 10^–10 × N^2.999 )和我们通过Doubling hypothesis方法得出的模型是很接近的。计算机中有很多的因素也会影响运行时间，但是关键因素一般和计算机的型号无关。影响因素关键的因素即为你使用的算法和数据. 决定幂定律中的 b 值还有很多与系统相关的因素：硬件配置：CPU，内存，缓存…软件环境：编译器，解析器，垃圾回收器…计算机的系统：操作系统，网络，其它应用…以上所有因素，包括关键因素，都决定了幂定律中的 a 值现代计算机系统中硬件和软件是非常复杂的，有时很难获得非常精确的测量，但是另一方面我们不需要像其他科学中需要牺牲动物或者向一颗行星发射探测器这些复杂地方法，我们只需要进行大量的实验，就能理解和得到我们想要知道的影响因子(的值)。数学模型待更新。。。 ...

写在前面咱不是计算机专业的，却一直对计算机算法感兴趣，也一直致力于减小自己程序的复杂度[捂脸]，昨日吃饭时，某老铁考我一道算法题，思索良久，辗转反侧，夜不能寐，遂厚着脸皮去问答案，然则令吾汗颜，果真是一波骚操作……看题！给定一个非空整数数组, 除了某个元素只出现一次以外, 其余每个元素均出现两次, 找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？示例 1:输入: [2,2,1] 输出: 1示例 2:输入: [4,1,2,1,2] 输出: 4看答案之前，不妨独立思考一下，看看能不能想出解决方案!推荐先想一会儿！如果实在想不出来, 可以看一下提示 继续想 ！！提示看一下标题！！！题目解析根据题目描述，由于加上了时间复杂度必须是O(n)，并且空间复杂度为O(1)的条件，因此不能用排序方法，也不能使用map数据结构。咱想了一晚上，结果, 答案是使用 位操作Bit Operation 来解此题。将所有元素做异或运算，即 a[1] ⊕ a[2] ⊕ a[3] ⊕…⊕ a[n]，而结果就是那个只出现一次的数字，时间复杂度为O(n)。什么？？你忘记了异或？？？异或运算 A ⊕ B 的真值表如下:ABA ⊕ BFalseFalseFalseTrueTrueTrueTrueFalseTrueFalseTrueTrue即:不相等即为True题目进阶有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。示例 :输入: [1,2,2,1,3,4] 输出: [3,4]题目再解析根据前面找 一个 不同数的思路算法，在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果, 为了叙述方便, 我们这里把这个结果简单记为字母 K 。因为这两个只出现一次的元素一定是不相同的，所以 K 一定不为零, 将K从左往右数的第一个为1的位记录下来。再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。这样就解出题目, 忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。举个例子吧假如:输入是: [1,2,2,1,3,4,7,7] 进行异或操作:>>> 1^2^2^1^3^4 # python的异或操作符7异或完毕为7即0000 0111数字7从左往右数的第一个为1的位为0000 0111 ^也就是第六位以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分(也就是数组大于等于4的分一组, 小于4的分一组)即[4, 7, 7] 和 [1,2,2,1,3]>>> # 数组[4,7,7]所有元素做异或操作>>> 4^7^74>>> 数组[1,2,2,1,3]所有元素做异或操作>>> 1^2^2^1^33大功告成！！据说此题来源于 LeetCode 第 136 号问题：https://leetcode-cn.com/probl… ...

题目给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。示例 1:输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3]输出: true示例 2:输入: 1 1 / \ 2 2 [1,2], [1,null,2]输出: false示例 3::输入: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2]输出: false题解大多数的二叉树题目都是用递归可以解的。所以当拿到二叉树的题目的时候，我们首先就是看看能拆解成哪些子问题。这个问题的子问题很简单，就是左子树，右子树都相等的二叉树是相同的二叉树。/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } /class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } else if (p == null || q == null) { return false; } if (p.val == q.val) { return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } else { return false; } }}那如果用非递归解怎么解呢?如果遇到二叉树的问题，没思路还有第二招，就是想想看是不是遍历的变种：先序遍历中序遍历后序遍历层次遍历我们可以用队列，一起进行层序遍历，同时比较左右两颗树:/* * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } else if (p == null || q == null) { return false; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(p); queue.add(q); while(!queue.isEmpty()) { TreeNode left = queue.poll(); TreeNode right = queue.poll(); if (left == null && right == null) { // 都是空的,遍历到叶子节点了 continue; } else if (left == null || right == null) { // 有一个为null return false; } else if (left.val != right.val) { // 不相等. return false; } // 左子树入队 queue.add(left.left); queue.add(right.left); // 右子树入队 queue.add(left.right); queue.add(right.right); } return true; }}其实我们本质上就是要比较左右两棵树,也没必要非要是队列,其实stack也是可以的,大同小异。所以并不是你记住哪种数据结构，关键是你能理解后，灵活应用. public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } else if (p == null || q == null) { return false; } Stack<TreeNode> stack = new Stack<>(); stack.push(p); stack.push(q); while(!stack.isEmpty()) { TreeNode left = stack.pop(); TreeNode right = stack.pop(); if (left == null && right == null) { continue; } else if (left == null || right == null) { return false; } else if (left.val != right.val) { return false; } stack.push(left.left); stack.push(right.left); stack.push(left.right); stack.push(right.right); } return true; }相关阅读技术文章汇总【Leetcode】98. 验证二叉搜索树【Leetcode】95~96 不同的二叉搜索树 ...

大O表示法使用大写字母O，可以认为其含义为"order of"（大约是）。我们可以使用大O法来描述线性查找使用了O(N)级时间，二分查找使用了O(log N)级时间，向一个无序数组中插入使用了O(1)，或常数级时间。下面的图总结了算法的运行时间： 通过图我们可以比较不同的大O值，O(1)是优秀，O(logN)是良好，O(N)是还可以，O(N^2)则很差了，比如冒泡排序。下面我们通过例子来看一下二分查找法。就是我们玩过的游戏猜数字，设定一个数组大小，一个人心里想一个数，让另外一个人来猜。每次告诉他猜大了还是小了，直到猜中为止。看花了多少步。/*** 二分查找法* @param search 要查找的数* @param total 数组长度*/public void compute(int search,int total){//设定的数组int[] num;if(total > 0 && search <= total && search >= 0){num = new int[total];for (int i = 0 ; i < total; i++){num[i] = i;}//花了多少次找到int sum = 0;//最小值int min = 0 ;//最大值int max = total;//当前猜的值int current;while (true){sum ++ ;current = (min + max) / 2;//打印猜的每个数System.out.println(current);if(num[current] == search){System.out.println(“找到了,花了” + sum + “次”);return;}else{//如果猜的数大于选定的数，则把max设为猜的数，否则把min设为猜的数if(num[current] > search){max = num[current] ;}else{min = num[current];}}}}else {System.out.println(“请输入大于等于0的正整数且查找的数不能大于数组里最大的数”);}}调用方法：compute(3,100) 执行结果：50251263找到了,花了5次 ...

递归算法大家应该都不陌生吧，其实最开始遇见递归应该是在数学课上，类似于f(x)=f(x-1)+f(x+1)，f(1)=1，f(2)=4，f(3)=3这种数学题大家应该见过不少，其实思想就是层层递归，最终将目标值用f(1)，f(2)，f(3)表示。之前做个一个需求，需要实现类似操作系统文件夹的功能，我们用MySQL数据库记录数据，表字段有4列，分别是id，index_name，pid，is_directory，index_name记录文件或文件的名字，pid记录它的父级id，is_directory标记它是文件还是文件夹。记录被存下以后，就涉及到取数据的问题了，我们前端需要的目标数据结构是这样的[{“id”:1,“name”:"./"},{“id”:2,“name”:"./1.txt"},{“id”:3,“name”:"./dir1/"},{“id”:4,“name”:"./dir1/2.txt"},…]有点类似linux系统的tree命令。第一版代码是这样的：tree = []def getTree(pid): returnfor index in childIndexes: if len(tree) == 0: if index.is_directory==1 tree.append({‘id’:index.id,’name’:’./’+index.index_name+’/’}) getTree(index.id) else: tree.append({‘id’:index.id,’name’:’/’+index.index_name}) else: for item in tree: if item[‘id’] == index.id if item.is_directory==1: tree.append({‘id’:index.id,’name’: item[’name’]+index.index_name+’/’}) else: tree.append({‘id’:index.id,’name’:item[’name’]+index.index_name})大概看一下这个算法的时间复杂度，第一层的遍历时间复杂度是n，第二层遍历的时间复杂度是n，内层的时间复杂度是O（n^2），再加上递归，最后的时间复杂度是O（2^nn^2），这个算法可见很粗糙，假如递归深度到是100，最后执行效率简直会让人头皮发麻。接下来我们考虑一下如何优化。第二版代码：tree = []def getTree(pid,path=’./’): return for index in childIndexes: if len(tree) == 0: if index.is_directory==1 tree.append({‘id’:index.id,’name’:path+index.index_name+’/’}) getTree(index.id, path+index.index_name+’/’) else: tree.append({‘id’:index.id,’name’:path+index.index_name}) else: if item.is_directory==1: tree.append({‘id’:index.id,’name’:path+index.index_name+’/’}) else: tree.append({‘id’:index.id,’name’:path+index.index_name})我们用变量保存每一次的path，这次我们看看时间复杂度是多少。第一层遍历时间复杂度是O(n)，加上递归，最后的时间复杂度是O(2^nn)，不算太理想，最起码比第一次好点。再看看一个面试的常见的题目，斐波拉契数列，n=1,1,3,5,8,13…，求第n位是多少？一看首先就想到了递归的方式：def fibSquence(n): if n in (1,2): return fibSquence(n-1)+ fibSquence(n-2)这个算法的时间复杂度是O(2^n)，关于时间复杂度具体看调用次数便能明白。我们考虑一下如何优化，比如求n=3是，需要先求n=2,n=1，但是最开始n=1,n=2已经求过，多了两步重复计算。下面是优化的代码：fibMap = {1:1,2:2}def fibSquence(n): else: result = fibSquence(n-1)+ fibSquence(n-2) fibMap.update({n:result}) return result我们用map报存中间值，map是基于hash实现的，时间复杂度是O(1)，这样这个算法的时间复杂度就是O(n)。但是事实上这个问题大可不必用递归方式求解fibMap = {1:1,2:2}def fibSquence(n): else: for i in range(3,n+1): fibMap.update({i:fibMap[i-1]+fibMap[i-2]}) return fibMap[n]这样我们只用一次遍历，便可以求出目标值。递归算法的优化大概就是避免重复运算，将中金状态保存起来，以便下次使用，从结构上来看，是将时间复杂度转换为空间复杂度来解决。递归算法的效率其实是非常低的，能不用递归就尽量不用递归；当然了也要具体问题具体对待，比如说开始提到我做的项目遇到的问题，不用递归我还真想不出其他更好的方式解决。作者：杨轶 宜信技术学院 ...

时间复杂度一直很迷。。。。 在网上找了看了一些博客，一句话，看不懂。。。。 于是自己去学了一下，总结为下面的。算法的效率，就是说一个算法的执行时间，它始终还是由我们执行每一行代码的次数来决定。我们可为每一个算法编写一个测试程序，然后拿到机器上去跑，但是由于除了算法本生，测试结果还受到很多其他因素的影响，列如cpu的执行速度等不确定因素，而且我们也不可能为了每一个算法去编写一个测试程序这样也不现实。所以后来人们采用事前估算的方法，依据统计学。这种情况下抛开了其他所有的不确定因素，一个算法的好坏由一个算法的好坏和输入规模来决定。例如:当n很大的时候，两种算法的差距就打了起来，第一个是2n+2次，第二个始终都是2次。上面的两个算法分别可以看做时间复杂度为n和1，下面来解释为什么是这样。时间复杂度研究算法的复杂度，侧重的研究输入规模很大的情况，在这种情况下我们就可以忽略一个复杂度中的一些小项，也就是执行次数特别大的情况，因为这样才能判定一个算法的在某种场景下的好与坏，这个时候就需要利用统计学知识。我们接下来通过大量的例子来解释。通过这几个例子为后面的算法时间复杂度做铺垫。例一将设A算法要做2n+3次计算，B需要做3n+1次操作，你觉得哪一个更快一点呢。下面来看看统计的结果。从结果来看最开始算法A1不及B1，当n等于5的时候，慢慢超过它，到后面完全胜过它，这就是输入规模的重要性，而且我们看A2、B2发现当输入规模很大的时候常数项可以完全忽略。函数的渐进增长: 给定两个函数，f(n)、g(n)，如果存在一个整数N当n>N的时候，f(n)总是比g(n)大,那么我们说f(n)的渐进增长比g(n)大。当例二算法C为4n+8,算法D为2n^2 + 8图上有错，第二张图为C1、C2, D1,D2。从观察当中可以可以发现，当n很大的时候，相乘的系数，影响也很小了，比如4n+8和n，在图上都重叠到一块儿去了，但是对于C1、C2，系数有影响，但是对比C、D算法的时候，可以看出系数并不影响比较。可以得出结论系数不影响两个算法之间的比较，因此也可以去掉。例三算法E为2n^2+3n+1，算法F为2n^3+3n+1通过图中对比E、F两个算法，可以看到指数对于测试结果影响很大。例四算法G为2n^2，算法H为3n+1,算法I为2n^2+3n+1因此我们可以得出结论: 判断一个算法的效率的时候，函数中的常数和次要项都可以忽略，而更应改关注最高项的介数。时间复杂度的计算用大写O()来作为时间复杂度的记法，称为大O记法那么我们怎么来推导大O阶呢。首先我们需要计算出程序执行的次数，再按照下面总结出来的方式来求解，这里的总结均来自前面的例子只有常数项，将常数看做1,得到O(1)对于多项表达式，只保留最高项，且去除与这个项相乘的常数其实就是这么简单。。。。，我在网上看到的其他文章语言实在太官方，明明简单的东西被这些糟老头子给整复杂了。下面来看几个计算的例子:上面的时间复杂度为O(1)时间复杂度为O(n)时间复杂度为o(n^2)上面的例子为对数阶。假设程序执行x次退出循环，那么可以得到等式2^x=n,所以当x=log(2底数)n的时候推出循环，执行次数为log(2)n + 1，所以可以得到最终结果为O(logn)还有一个空间复杂度，空间可以换取时间，时间也可以换取空间，在实际当中往往要在二者之间达到一个平衡

（二）算法算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。2.1 算法的特性算法具有五个基本特性。输入 算法具有零个或多个输入输出 算法至少有一个或多个输出有穷性 算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且一个步骤在可接受的时间内完成。确定性 算法的每一个步骤都具有确定的含义，不会出现二义性。可行性 算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。2.2 算法设计的要求正确性 算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。 大体分为以下四个层次： 1 算法程序没有语法错误。 2 算法程序对于合法的输入数据能够产生满足要求的输出结果。3 算法程序对于非法的输入数据能够得出满足规格说明的结果。 4 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。 一般情况，以层次3作为一个算法是否正确的标准。 可读性 算法设计的另一目的是为了便于阅读、理解和交流。健壮性 当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。时间效率高和存储量低 设计算法应该尽量满足时间效率高和存储量低的需求。2.3 算法效率的度量方法算法效率大都指算法的执行时间，通过对算法的数据测试，利用计算机的计时功能，来计算不同算法的效率是高还是低。2.3.1 事后统计方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。缺陷：必须依据算法事先编制好程序，需要花费大量的时间和精力。时间的比较依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣。算法的测试数据设计困难，程序的运行时间往往还与测试数据的规模有很大关系，效率高的算法在小的测试数据面前得不到体现。基于事后统计方法有上述缺陷，不予采纳。2.3.2 事前分析估算方法在计算机程序编制前，依据统计方法对算法进行估算。 算法执行时间的受影响因素 1 算法采用的策略、方法 算法好坏的根本2 编译产生的代码质量 软件支持3 问题的输入规模 输入量的多少4 机器执行指令的速度 硬件性能PS: 抛开与计算机硬件、软件有关的因素。一个算法的运行时间，依赖于算法的好坏和问题的输入规模。我们不关心编写程序的设计语言，也不关心程序跑在什么计算机中，我们只关心它所实现的算法。最终，在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。综上所述，测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数。运行时间与这个计数成正比。而我们在分析一个算法的运行时间时，重要的是把基本操作的数量与输入规模关联起来，即基本操作的数量必须表示成输入规模的函数。举例：1 + 2 + 3 + … + n 求和算法算法 输入规模 基本操作的执行次数（输入规模的函数）遍历1到n累加 n f(n) = n (1 + n) * n / 2 n f(n) = 1 2.4 函数的渐近增长函数的渐近增长：给定两个函数 f(n) 和 g(n)，如果存在一个整数 N，使得对于所有的 n > N，f(n) 总是比 g(n) 大，那么，我们说 f(n) 的增长渐近快于 g(n)。两个算法函数进行比较时，随着 n 的增长，我们发现如下几点规律：加法常量可以忽略。与最高次项相乘的常数并不重要。最高次项的指数大的，函数随着 n 的增长，结果也会增长的特别快。综上所述，判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。判断一个算法的好坏，少量的数据是不能做出准确判断的。某个算法，随着n的增大，它会越来越优于另一个算法，或者越来越差于另一个算法。即事前估算方法的理论依据，通过算法时间复杂度来估算算法时间效率。2.5 算法时间复杂度在进行算法分析时，语句总的执行次数 T(n) 是关于问题规模 n 的函数，进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n) = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和 f(n) 的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中 f(n) 是问题规模 n 的某个函数。这样用大写O()来体现时间复杂度的记法，称之为大O记法。2.5.1 推导大O阶方法用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中，只保留最高阶项。如果最高阶项存在且不是1，则去除与这个项相乘的常数。2.5 常见的时间复杂度执行次数函数 f(n) 阶 O(f(n)) 非正式术语12 O(1) 常数阶6n^3 + 2n^2 + 3n + 4 O(n3) 立方阶3n^2 + 2n + 1 O(n^2) 平方阶5log2(n) + 20 O(logn) 对数阶2n + 3nlog2(n) + 19 O(nlogn) nlogn阶6n^3 + 2n^2 + 3n + 4 O(n^3) 立方阶2^n O(n^2) 指数阶常用时间复杂度所耗费的时间 从小到大依次是:O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)2.6 最坏情况与平均情况查找一个有n个随机数字数组的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为 O(1) ,但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是 O(n) ,这是最坏的一种情况。最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。2.7 算法空间复杂度我们在写代码时，完全可以用空间来换取时间。算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作： S(n) = O(f(n)) ,其中， n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数。通常，我们都使用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度时”，通常指时间复杂度。 ...