最近在 LeetCode 的讨论区发现好多同学在求助，因为他们遇到了一些真题，不知道如何处理。 比如一道和堆相关的真题。...，时间复杂度为 O(n^3m^3) 。...pre_sum_mat[b+1][c] - pre_sum_mat[a][d+1]) 上述计算的时间复杂度为O(1)，因此这种做法规避了暴力解对子矩阵求和时出现的反复计算，降低了最内层求和时时间复杂度...该过程的时间复杂度为 O(nm) 。...时间复杂度： O(n^2m^2) 空间复杂度： O(nm) 二维前缀和矩阵所占空间。
没看过的建议先去看先导篇前端如何搞定数据结构与算法(先导篇) 不过没关系，至少是有同学在评论区反馈期待下一篇的，那就要坚持把这个系列写下去，今天来给大家聊一聊在数据结构与算法中占了半壁江山的概念。...冒泡排序、插入排序、选择排序的时间复杂度都是 O(n^2)。 至于 O(n^3) 就是在 O(n^2) 的基础上再嵌套一层循环。...在现实中，往往代码会比较复杂，这里总结了几条判断时间复杂度的小技巧送给你： 单段代码看高频：循环 多段代码取最大：有循环和多重循环的情况，取多重循环的复杂度 嵌套代码求乘积：循环中的递归 多个规模求和：...「如果初始化一个二维数组 n*n，那么它的空间复杂度就是 O(n^2)。」 除此之外，O(logn)、O(nlogn) 这样的对数阶空间复杂度在平时也很少见，这里不再展开。...「一般在实际中，空间复杂度和你初始化的数组长度有关。除此之外，也和递归的深度有关。」 时空转换 时间复杂度和空间复杂度往往是相互影响的，两者不可得兼。
一个算法的好坏影响到了很多实际性的问题，在程序中效率是极其重要的，一个算法的评价主要从时间复杂度和空间复杂度来考虑。...所以我们在讨论时间复杂度的时候，仅仅从理论角度，也就是视作计算机的环境不变，来进行讨论。 影响算法时间代价的具体有两个方面：问题规模和语句频度。...步骤3：分析每部分的操作次数 步骤4：累加所有部分的操作次数 分析这里的操作次数，我们可以使用更为简单的方法，请注意，这里的for循环中还嵌套了一个for循环，那么我们可以理解为：在进行大循环的时候，也会进行一次小循环...如何理解和应用复杂度分析 理解复杂度分析的核心是**能够评估算法在最坏、最好和平均情况下的性能。**这有助于我们在开发过程中选择最合适的算法和数据结构以确保程序的高效运行。...注意：在空间复杂度的计算中，大部分都是O(n)和O(1)，这两个复杂度是最为常见的。 如何理解和应用复杂度分析 理解复杂度分析的核心是**能够评估算法在最坏、最好和平均情况下的性能。
，如 ，省去最高阶项的系数后，成为 ； 分析时间复杂度的方法 总结起来，对于如何分析一段代码的时间复杂度，主要有如下 3 个实用方法： 只关注循环执行次数最多的一行代码； 加法原则：总复杂度等于量度最大的那段代码的复杂度...； 乘法原则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积； 常见的时间复杂度曲线 ?...常见时间复杂度 即无论执行多少行，都不会影响到其他区域，此时代码的复杂度就是 ，如下面的代码中，假设执行每行代码时间都相同切为 ，则 2,3 行各需 1 个执行时间，即为 $t + t =...arr.length 次，因此所需要的时间和数组长度成正比的，因此可以用 来表示它的时间复杂度。...的代码嵌套循环一次，此时复杂度就变成了 ，表现出来就是三重循环嵌套的形式。
，极大的优化了查找的复杂度 接下来我们来看看如何计算时间、空间复杂度！...O(log(n)) while (i < n) { console.log(i); i *= 2; } 对于 log(n) 的情况，在个时间复杂度是很好的，当然 O(1) 是最好的，但是在解题的时候...O(n^2) int arr = [][]// 遍历赋值 声明一个二维数组，填满值，它的空间复杂度就是 O(n^2) ，你可以理解为一个矩阵，n*n 为 n^2 总结 复杂度计算按最高阶来计算 时间、...空间复杂度描述的都是随数据规模的变化趋势 时间复杂度的重点在于循环嵌套 空间复杂度关注于内存 博主有话说 关于如何学习数据结构和算法，以及前端仔为什么要学算法？...，这样可以保证我们的刷题质量，同时把大量的时间花在刷算法题上是很不可取的噢～每天抽一点时间写 2，3 道这样慢慢积累，循循渐进～ 3.
这种优良的时间复杂度使得归并排序在处理大规模数据时具有显著优势。 再次是空间复杂度。归并排序的空间复杂度为O(n)，因为它需要额外的空间来合并两个已排序的子数组。...归并排序是一种分治算法，首先将原始数组递归地分成两个子数组，然后对子数组进行排序，最后将排序好的子数组合并成一个有序数组。 代码中的MergeSort函数是对外接口，用于调用归并排序算法。...然后定义一个变量gap作为当前的步长，初始时为1。通过一个循环，每次将gap乘以2，直到gap大于等于n。在循环中，通过两个内嵌的循环，将数组分成若干个子数组，并进行两两合并。...内层循环中，先计算出两个待合并的子数组的起始和结束位置，然后对这两个子数组进行合并操作。合并过程中，比较两个子数组中的元素，将较小的元素放入临时数组tmp中，并移动对应子数组的指针。...最后，将tmp中的结果拷贝回原始数组a中。 整体的时间复杂度为O(nlogn)，空间复杂度为O(n)。由于该排序算法是稳定的，所以适用于各种类型的数据排序。
引言 在现代计算机科学和编程中，算法的效率至关重要。算法效率不仅影响程序的运行时间，还直接关系到程序的内存使用情况。为了评估和优化算法，我们常用两个主要指标：时间复杂度和空间复杂度。...本文将详细介绍这两个概念，并通过C语言示例来解释它们的实际应用。 一、算法效率的基础 在算法设计中，我们先后追求以下两个层面的目标。 1....二、时间复杂度 1.概念 时间复杂度（Time Complexity）用来衡量算法执行所需时间如何随着输入规模的增长而变化。它帮助我们评估算法在处理大数据量时的表现。...平方阶通常出现在嵌套循环中，外层循环和内层循环的时间复杂度都为 () ，因此总体的时间复杂度为 ( 2 ) ： /* 平方阶 */ int quadratic(int n) { int count...而通过对数换底公式，我们可以得到具有不同底数、相等的时间复杂度： 也就是说，底数 可以在不影响复杂度的前提下转换。
..+1 就是等差数列求和(n-1+1)*(n-1)/2 在这个结果中对结果影响最大的是N^2,所以这个代码的时间复杂度就是O(N^2) */ 冒泡排序的时间复杂度为O(N^2) void func5...所以在提交的时候我们会遇到超出时间限制的错误 既然这里的时间复杂度是O(N^2),空间复杂度是O(1) 那我们能不能先办法将时间复杂度降到O(N)呢？...] = nums[4]; 将原先数组的下标为4的数字放到新数组的地址个位置 通过这个代码我们就实现了将原数组后k个数放到新数组的前k个位置， 将原数组的剩下的4个数据放到新数组的后4个位置 在后面的循环中...，我们就将新数组中的值重新拿回到原数组内，因为我们打印的是原数组，在原数组中进行改变 */ 那么这个代码的时间复杂度是多少呢？...在第一个循环中，时间复杂度是O(N),在第二个循环中时间复杂度是O(N) 那么总的时间复杂度就是O(2N)，根据规则，消掉系数，那么最后的时间复杂度就是O(N) 这种方法的时间复杂度就达到了O(N) 但是这种思路的空间复杂度也是
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积 落实到具体的代码上，我们可以把乘法法则看成是嵌套循环 int cal(int n) { int ret = 0; int i = 1...最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度 最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度 平均情况时间复杂度 // n表示数组array的长度 int find...当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置 然后再将新的数据插入。...但如果数组一开始就有空闲空间，则直接将数据插入数组 最理想的情况下，数组中有空闲空间，我们只需要将数据插入到数组下标为 count 的位置就可以了，所以最好情况时间复杂度为 O(1) 最坏的情况下，数组中没有空闲空间了...，我们需要先做一次数组的遍历求和，然后再将数据插入，所以最坏情况时间复杂度为 O(n) 平均时间复杂度是O(1): 假设数组的长度是 n，根据数据插入的位置的不同，我们可以分为 n 种情况，每种情况的时间复杂度是
O(n^2) - 二次时间复杂度 这种复杂度通常出现在嵌套循环中。...在选择算法时，需要根据具体问题的需求和约束来权衡时间复杂度和空间复杂度。 五：优化时间复杂度和空间复杂度 优化时间复杂度的策略是提升算法执行效率的重要手段，以下是一些具体的策略： 1....在实际应用中，需要根据具体问题的需求和约束来权衡这些因素，以达到最佳的空间优化效果。 7：时间复杂度和空间复杂度的重要性： 时间复杂度和空间复杂度在算法设计和分析中扮演着至关重要的角色。...它们不仅决定了算法在不同规模问题上的执行效率，还影响着算法在实际应用中的可行性和性能。 时间复杂度的重要性 性能评估：时间复杂度是衡量算法执行时间随输入规模增长而变化的指标。...量子算法在某些问题上的表现优于经典算法，未来的研究将探索如何将量子计算与传统优化方法结合，以进一步提高算法的性能。
性能测试之类的对吧-----> 主机的性能不同，数据的准确性和数据量等等 ，都会对我们的结果产生影响。 作为开发人员如何评估下呢？...等等 ---- 如何计算时间复杂度 算法的时间复杂度，主要看算法中使用到的循环结构中代码循环的次数（称为“频度”）。次数越少，算法的时间复杂度越低。...平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。 最好时间复杂度是指在最好情况下，算法的时间复杂度。...一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。...---- 线性对数阶O(nlogN) 理解了 线性对数阶O(logn) ， 再来看 O(nlogN) 就很容易理解了—> 将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n *
1.4 常见时间复杂度 即无论执行执行多少行，都不会影响到其他区域，此时代码的复杂度就是 void sayHello(String name){ System.out.prinln("Hello...arr.length 次，因此所需要的时间和数组长度成正比的，因此可以用 来表示它的时间复杂度 int sum(int[] arr){ int total = 0; for(int...m < n ){ m *= 2; } } } 假设我们将时间复杂度为 的代码重复执行 次，那么此时的时间复杂度就是 ，即可表示为 ，表现出来就是双重循环的形式 void...的代码嵌套循环一次，此时复杂度就变成了 ，表现出来就是三重循环嵌套的形式 void demo(int n){ for(int i = 0; i < n; i++){ for(...空间复杂度 2.1 定义 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度（即除开原始序列大小的内存，在算法过程中用到的额外的存储空间），反映的对内存占用的趋势，而不是具体内存，用 来代替
局部性分类 局部性主要分为时间局部性和空间局部性。 时间局部性：最近使用过的数据和指令在不久的将来可能再次被使用。具体如下图所示。 ?...在应用程序的设计中，Web浏览器将最近被引用的文档放在本地磁盘上，利用的就是时间局部性。作为程序员应该理解局部性原理，一般来说，有良好局部性的程序比局部性差的程序运行得更快。...首先我们要知道数组在内存中是以行优先的方式存储的。SumArrRow函数在for循环中访问a的顺序如下。...SumArrCol函数和SumArrRow函数，唯一的区别是我们交换了i和j的循环。这样交换循环对它的局部性有何影响？因为它按照列顺序来扫描数组，而不是按照行顺序。...对于循坏体中的每个变量，这个函数要么有好的空间局部性，要么有好的时间局部性，所以我们可以断定 SumArr函数有良好的局部性。
Subarray Sum Equals K 和为K的子数组（Medium） 在设计算法时，时间复杂度始终是我们关注的重点。我们需要让算法的时间复杂度尽可能低，追求运行效率。...Range Sum Query - Immutable（Easy） image.png 这道题目的解法很直白，难点在于如何减少时间复杂度。我们来看看不同的解法的时间、空间复杂度有何区别。...在 sumRange 会被调用很多次的情况下，我们要尽可能地减少一次调用的时间。...可以看到，前缀和方法的特点是：能优化时间复杂度，同时让空间复杂度不会太大。这让前缀和成为一个很实用的数组预处理手段。 前缀和的应用 下面，我们用两道典型题目来看看前缀和的应用场景。...和为K的子数组。这两道题目都有一个共同点：对子数组求和。我们在做题的时候，只要遇到与「子数组求和」相关的题目，就考虑一下使用前缀和方法会如何，一定没有错。
程序是由一个个函数组成的，有些简单的由几个基础运算组成的函数大家一眼就能看出来它的时间复杂度，但是大部分函数没那么简单，只要函数里面涉及到了循环、外部函数调用甚至递归的时候它的时间复杂度就没那么容易分析啦...要分析程序的时间复杂度，首先还是要确定时间复杂度的度量标准— —英文文档里通常会用 metric 这个单词来表示，这个标准规定了在函数中平铺展开的代码、循环中的代码、有函数调用的代码、以及递归调用的代码的时间复杂度的测量方式...Big O Notations 如何计算程序的时间复杂度呢？最常用的度量方式叫做 Big O Notations 翻译过来叫大O标记法。...使用大O标记法前要先了解它的几个要点： 相同配置的计算机进行一次基本运算的时间是一定的，因此我们将程序基本运算的执行次数作为时间复杂度的衡量标准。...statement2; statement3; } } 假设循环中的语句都是基础操作，没有对函数的调用，那么这个代码有两层嵌套循环，时间复杂度为O(n2)。
时间复杂度分析 在计算机程序编写前，依据统计方法对算法进行估算，经过总结，我们发现一个高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素： 1.算法采用的策略和方案； 2.编译产生的代码质量...我们不关心编写程序所用的语言是什么，也不关心这些程序将跑在什么样的计算机上，我们只关心它所实现的算法。...下面我们使用大O表示法来表示一些求和算法的时间复杂度： 算法一： public static void main(String[] args) { int sum = 0;//执行1次...，那么当输入规模为n时，以上算法执行的次数分别为： 算法一：3次 算法二：n+3次 算法三：n^2+2次 如果用大O记法表示上述每个算法的时间复杂度，应该如何表示呢？...，就需要执行100*100次，也就是n的平方次，所以这段代码的时间复杂度是O(n^2). 3.立方阶 一般三层嵌套循环属于这种时间复杂度 public static void main(String[]
（3） 换个思路，我们将所有遍历过的值存放起来，每次遍历到一个新的值b时，我们可以查找目标值减去值b是否在我们存放的值中。...基于哈希表的特性，查找的时间复杂度为O（1），总时间复杂度就变为了一次for循环O（n） 回到本道题中: （1） 由于需要返回对应的索引，所以需要使用HashMap（在python中是dict），key...存放数组中的值，value存放数组中的索引，遍历数组，将遍历过的值存入dict，如果目标值减去当前值在dict中则证明找到了目标值。...双指针 （1） O(nlogn)-主要是快排的影响 （2） 在一个有序的数组中最左边一定是最小值，而最右边一定是最大值。...，下一文将引申这两种方法在三个数求和中的应用。
3.所有其他操作都是不受循环影响的常数时间操作，因此我们可以将所有这些操作作为C2的累计常量。 总运行时间f(N)=C1×N+C2，是一个与N相关的函数。 让我们把N放大。...我们之前提到过，算法中有一个嵌套循环。对于第一个循环中的每个变量值，我们知道在第二个循环中所花费的时间。现在剩下的就是给这些加和。...时间复杂度：从步骤1和4开始，在for循环中有一个嵌套的while结构。 while循环运行j + 1次，其中j依赖于i。让我们看看j的值如何随着i的变化而变化。...第2-3步将元素从原始数组复制到临时缓冲区，我们使用此缓冲区进行合并。已排序的元素将被复制回原始数组。由于我们会遍历数组的某个部分，假设该数组有N个元素的话，该操作的时间复杂度为O(N)。...在本文中，我们介绍了复杂性分析的概念，它是算法设计和开发的重要部分。我们看到为什么分析算法的复杂性很重要，以及它如何直接影响我们的最终决策。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
云直播
