开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

如果循环变量除以/乘以一个常量，为什么我们认为时间复杂度为O(Logn)？

循环变量除以/乘以一个常量，为什么我们认为时间复杂度为O(Logn)？

时间复杂度是用来衡量算法执行时间随输入规模增长而增长的速度。在这个问题中，循环变量除以/乘以一个常量，我们认为时间复杂度为O(Logn)的原因如下：

循环次数随着输入规模的增长而减少：当循环变量除以/乘以一个常量时，每次循环后循环变量的值会发生变化。如果除以一个常量，循环变量的值会逐渐减小；如果乘以一个常量，循环变量的值会逐渐增大。这意味着随着输入规模的增长，循环次数会减少。
每次循环的操作规模减少一半：由于循环变量除以/乘以一个常量，每次循环后操作的规模会减少一半。例如，如果循环变量除以2，那么每次循环后操作的规模会减少一半。这种减半的操作规模使得算法的执行时间不会线性增长，而是以对数的方式增长。

综上所述，当循环变量除以/乘以一个常量时，我们认为时间复杂度为O(Logn)，其中n表示输入规模。这种时间复杂度表示算法的执行时间随着输入规模的增长而以对数的方式增长。

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

Leetcode算法系列| 9. 回文数

如果我们把最后一位数字乘以 10，再加上倒数第二位数字，1 * 10 + 2 = 12，就得到了我们想要的反转后的数字。如果继续这个过程，我们将得到更多位数的反转数字。...return x == revertedNumber || x == revertedNumber / 10; } } 时间复杂度：O(logn) 对于每次迭代，我们会将输入除以 10，因此时间复杂度为...空间复杂度：O(1) 我们只需要常数空间存放若干变量。...return x == revertedNumber || x == revertedNumber / 10; } } 时间复杂度：O(logn) 对于每次迭代，我们会将输入除以 10，因此时间复杂度为...空间复杂度：O(1) 我们只需要常数空间存放若干变量。

1171 0

数据结构与算法之美 - 时间和空间复杂度

所以上面代码的时间复杂度为 O(log2n)。实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。为什么呢？...因此，在对数阶时间复杂度的表示方法里，我们忽略对数的 “底”，统一表示为 O(logn)。...最好情况时间复杂度，最坏情况时间复杂度 如果数组中第一个值就等于 x，那么时间复杂度为 O(1)，如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)。...省略掉系数、低阶、常量，所以，这个公式简化之后，得到的平均时间复杂度就是 O(n)。我们知道，要查找的变量 x，要么在数组里，要么就不在数组里。...，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 newArr ，是个空数组。

4314 0

数据结构算法入门--一文了解什么是复杂度

按照数量级递增，常见的时间复杂度量级有：常量阶 O(1) 对数阶 O(logn) 线性阶 O(n) 线性对数阶 O(nlogn) 平方阶 O(n^2)，立方阶 O(n^3)…k次阶 O(n^k) 指数阶...a = 3 b = 4 print(a + b) O(logn)、O(nlogn) O(logn) 也是一个常见的时间复杂度，下面是一个 O(logn) 的代码例子： i = 1 count = 0...假如上述代码进行简单的修改，将 i *= 2 修改为 i *= 3 ，那么同理可以得到时间复杂度就是 ? 。但在这里，无论是以哪个为对数的底，我们都把对数阶的时间复杂度记为 O(logn)。...，常量 ? 基于前面的理论，系数可以被忽略，也就是这里的常量 C 可以忽略基于这两个原因，对数阶的时间复杂度都忽略了底，统一为 O(logn) 。...简单介绍下一个程序所需要的空间主要由以下几个部分构成：指令空间：是值用来存储经过编译之后的程序指令所需要的空间。数据空间：是指用来存储所有常量和变量值所需的空间。

5981 0

搞编程，你必知必会的复杂度分析

首先我们先来弄清楚我们为什么需要做复杂度分析。 为什么需要复杂度分析？真实的时间复杂度、空间复杂度我们需要在机器上执行我们编写的代码，才能统计出我们的代码这这个环境下的真实时间复杂度、空间复杂度。...而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，所以我们示例中的总时间就可以用 T(n) =O(n) 来标识。...1、只关注循环执行次数最多的一段代码我们知道用大O公式来表示时间复杂度的时候，忽略了常量、低阶、系数等，我们只需要关注循环执行次数最多的那一段代码就可以了，这段代码执行的次数 n 就是整个代码块的时间复杂度...常数阶O(1) 常数阶非常简单，就是没有变量，都是常量，那样代码的时间复杂度就为 O(1)。下面两段代码的时间复杂度都为 O(1)。...不一定的，如果数组中第一个元素正好是要查找的变量x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是O(1)。

4266 0

数据结构与算法之美 - 时间和空间复杂度

所以上面代码的时间复杂度为 O(log2n)。实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。为什么呢？...因此，在对数阶时间复杂度的表示方法里，我们忽略对数的 “底”，统一表示为 O(logn)。...最好情况时间复杂度，最坏情况时间复杂度 如果数组中第一个值就等于 x，那么时间复杂度为 O(1)，如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)。...省略掉系数、低阶、常量，所以，这个公式简化之后，得到的平均时间复杂度就是 O(n)。我们知道，要查找的变量 x，要么在数组里，要么就不在数组里。...，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 newArr ，是个空数组。

3634 0

剑指Offer题解 - Day45

1 / res : res; }; 时间复杂度 O(n)。空间复杂度 O(1)。分析：这样处理确实简单粗暴，但是无法通过提交。...因为当n很大的时候，会进行太多次的循环次数，最终就会超出时间限制。因此此方法「不可取」。二分法通过二分的方式可以将时间复杂度由O(N)降低至O(logN) 。...result; }; 时间复杂度 O(logn)。...如果说n就是偶数，那么上述的两步操作和不对指数进行除以 2 直接计算得出的结果是一样的。如果说n是奇数，需要再对结果乘以x，两者才相等。如此计算，就可以将时间复杂度降低至O(logn)。...复杂度方面，二分的时间复杂度为对数级别。result变量占用常数级别大小的额外空间。

2161 0

算法读书笔记(1)-时间、空间复杂度分析

我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了加法法则：总复杂度等于量级最大的那段代码的复杂度...，每循环一次就乘以 2。...如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了 O(nlogn) 也是一种非常常见的算法时间复杂度。...要查找的变量 x 可能出现在数组的任意位置。如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是 O(1)。...但如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)。

4432 0

复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？

所以，我们只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。...实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。为什么呢？...因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。如果你理解了我前面讲的 O(logn)，那 O(nlogn) 就很容易理解了。还记得我们刚讲的乘法法则吗？...如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。...，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。

9152 0

算法复杂度

我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n2)。...三.时间复杂度分析 3.1 只关注循环执行次数最多的一段代码大O这种复杂度表示方法只是一种变化趋势。我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。...对数级 O(logn)、O(nlogn) i=1; while (i <= n) { i = i * 2; } 从代码中可以看出，变量i的值从1开始取，每循环一次乘以2。...就像刚举的那个例子，如果数组中没有要查找的变量 x，我们需要把整个数组都遍历一遍才行，所以这种最糟糕情况下对应的时间复杂度就是最坏情况时间复杂度。 3.6 平均情况时间复杂度 还是用3.5的示例。...我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值，即：时间复杂度的大 O 标记法中，可以省略掉系数、低阶、常量，所以，咱们把刚刚这个公式简化之后

1622 0

算法的时间与空间复杂度（一看就懂）

「大O符号表示法」，这段代码的时间复杂度为：O(n) ，为什么呢?...，因此，我们可以简化的将这个算法的时间复杂度表示为：T(n) = O(n) 为什么可以这么去简化呢，因为大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。...对数阶O(logN) 还是先来看代码： int i = 1; while(i<n) { i = i * 2; } 从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i...因此这个代码的时间复杂度为：O(logn) 线性对数阶O(nlogN) 线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(...空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：空间复杂度 O(1) 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

8142 0

时间与空间复杂度介绍

，都可以用O(1)来表示它的时间复杂度 对数阶O(logN) int i = 1; while(i<n) { i = i * 2; } 在while循环里面，每次都将 i 乘以 2，乘完之后，i...因此这个代码的时间复杂度为：O(logn) 线性阶O(n) for(i=1; i<=n; ++i) { j = i; j++; } 这是最常用的循环代码片段，for循环里面的代码会执行n遍，...nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。...一、空间复杂度 和时间复杂度类似，空间复杂度常见的量级有如下 -空间复杂度 O(1) int i = 1; int j = 2; ++i; j++; int m = i + j; 如果算法执行所需要的临时空间不随着某个变量...n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1) 代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 O(1) 空间复杂度 O(n) int[] m = new

2631 0

算法笔记（八）：复杂度分析（二）

log3n） = O（log32*log2n） = O（C*log2n），其中C是常量，根据渐进符号的定义，计算时间复杂度时，我们可以忽略常量，所以上面这段代码的时间复杂度也是O（logn），同理，所有对数阶时间复杂度的表示中...，可以同一表示为O（logn）。 ...如果一段代码的时间复杂度是O（logn），如果循环运行n次，那么时间复杂度就是O（nlogn）。...（二）空间复杂度 下面这段代码，和分析时间复杂度一样，因为只有第三行代码创建了一个大小为n的数组，其他不是常量就是不占用内存空间，所以这段代码的时间复杂度是O（n） 1 def test1(n):...如果第一个元素就是我们要查找的元素，那么代码的时间复杂度就是O（1）最坏时间复杂度：如果最后一个元素才是我们要查找的元素，或者数组中根本就没有我们要查找的元素，那么代码的时间复杂度就是O（n）平均时间复杂度

9882 0

数据结构与算法 --- 复杂度分析专题（一）

如果用大 O 表示法表示上面的两个复杂的则是这样： T(n)=O(n) T(n)=O(n^2) 时间复杂度的分析方法大O复杂度表示方法只表示一种变化趋势，我们通常会忽略公式中的常量，低阶和系数，只记录最大量级...，因此，我们在分析一段代码时间复杂度的时候，我们也只需要关注「循环执行次数最多的那段代码」。...第二段，复杂度为 O(n) 。第三段，复杂度为 O(n^2) 。第四段，只执行一次，复杂度记为 O(1) 。「为什么第一段复杂度为常数？」...由上述代码中可以看出，变量i从1开始取值，每循环一次就乘以2，当i值大于n时，循环结束。...那如果我们把上述代码段中的i *= 2 修改为i *= 3，得到的时间复杂度就变成了 O(log_3n) 那为什么标题中的表示的时间复杂不体现对数的底数呢？

3312 0

算法—时间复杂度

你可能思路已经非常清晰了，满百除四百，不满除以4。额，先不要急。我们来看看还能不能进一步提高性能，降低时间复杂度。也就是用空间复杂度来换取时间复杂度。...比如，如果使用我们程序的用户，只会查看当前年份未来几年和过去几年的日历的话，我们完全可以使用一个比如：2100个元素的数组，每个元素为0或1，分别表示平年和闰年。...第x次循环，number = 2^x 也就是2^x=n得出x=log₂n。因此它的复杂度为O(logn)。...O(Log2N)； 2.4:O(nlogn)—线性对数阶上面看了二分查找，是LogN的（LogN没写底数默认就是Log2N)；线性对数阶就是在LogN的基础上多了一个线性阶；比如这么一个算法流程...最高阶参考上面列出的按增长量级递增排列，于是只需要保留result = (n^2)/2 3.如果最高阶项存在且不是1，去掉与这个最高阶相乘的常数得到时间复杂度 除以2相当于是乘以二分之一，去掉它，就得到

2.4K4 0

算法复杂度O(logn)详解

一.O(logn)代码小证明我们先来看下面一段代码: int cnt = 1; while (cnt < n) { cnt *= 2; //时间复杂度为O(1)的程序步骤序列 } 由于...cnt每次在乘以2之后都会更加逼近n，也就是说，在有x次后，cnt将会大于n从而跳出循环，所以 (2 ^ x = n) , 也就是 (x = log_2n) ，所以这个循环的复杂度为O(logn) 二....典型时间复杂度 $c$ 常数 $logN$ 对数级 $log ^ 2N$ 对数平方根 $N$ 线性级 $NlogN$ $N ^ 2$ 平方级 $N ^ 3$ 立方级 $2 ^ N$ 指数级由此我们可以得知...1 1 的结果 $$库里有两个常量M_E和M_PI M_E代表的是自然对数的底数e M_PI代表的是圆周率π 最后，也是最基本的最重要的当题目的数据范围达到了 (10^{18}) 的时候，很显然就要用...O(logn)的算法或数据结构了

3.1K4 0

2.时间复杂度与空间复杂度

所以，我们只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。...实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。为什么呢？...因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。如果你理解了我前面讲的 O(logn)，那 O(nlogn) 就很容易理解了。还记得我们刚讲的乘法法则吗？...如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。...所以，对于空间复杂度，掌握刚我说的这些内容已经足够了。空间复杂度 O(1) 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。

6932 0

你应该认识一下时间复杂度和空间复杂度

log2n，因此这个代码的时间复杂度为O(logn)。...这儿有个问题，为什么明明应该是O(log2n）,却要写成O(logn)呢？...其实这里的底数对于研究程序运行效率不重要，写代码时要考虑的是数据规模n对程序运行效率的影响，常数部分则忽略，同样的，如果不同时间复杂度的倍数关系为常数，那也可以近似认为两者为同一量级的时间复杂度。...O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。...三、空间复杂度计算空间复杂度 O(1) 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。

4151 0

算法之旅:复杂度分析

由于这是算法第一篇，所以我们先从简单的复杂度说起。任何算法都离不开复杂度分析，衡量一个算法的强与弱，其中一个比较统一的标准就是看它们之间的复杂度。你可能会有所疑问，为什么要看复杂度呢？...简单来说就是找到你认为最复杂的那段代码，或者说循环次数最多的那段代码。在大O表示法中已经说了，计算时间复杂度都会忽略常数、系数与低价，所以我们只需关注次数最多的那行代码。...，如果处在多个规模的变量，就直接按照正常的加法运算进行保留即可。...我们已经对O(n)与O(n^2)进行了举例，至于常数阶O(1)就不多说了，只要它没有循环体或者递归存在，那它的时间复杂度就是O(1) 下面再来分析下O(logn)与O(nlogn) 对数阶与线性对数阶...其中k是常量可以进行忽略，所以转化之后它们都是O(log2^n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的底，统一表示为O(logn)。

3551 0

1.说说你不知道的时间复杂度

一、为什么要学习数据结构和算法其实，以前我们都会说，学习数据结构有多么多么的重要，长篇大论。这次，我们java程序员来看看数据结构和算法重要性。例题：判断一个数是否是2的n次方。...如果是已经确定的，那么就不用计算了，常量就是我们说的不用计算的一种。 > 常数：O(1) 1表示的是常数。...其实我们要求的就是：循环多少次，i<= a 呢？2^n = a ; 求n=log2a, log以2为底a的对数。以上是O(logn)的情况，那么什么情况下使用O(nlogn)呢？...O(n) n是几就运行几次. n是未知的,不确定的.如果n是确定的,就是常量了. 时间复杂度就是O(1) } } 这里面a = a + 1;这句话会运行多少次呢？...如果一个数除以2，最后余数是0，那么这个数就是2的n次方；如果余数是1，那么就不是。

4181 0

来来来，让咱重新认识一下算法的复杂度！

常见时间复杂度 量阶表示常量阶 O(1) 对数阶 O(logn) 线性阶 O(n) 线性对数阶 O(nlogn) 平方阶、立方阶、k次方阶 O(n^2)、O(n^3)、O(n^k) 指数阶 O(2^...假如每循环 1 次变成乘以 3，如下所示 i = 1; while (i <= n) { i = i * 3; } 可得，时间复杂度为。...O(nlogn) 的时间复杂度就相当于上面说到的“乘法法则”：一段代码的时间复杂度为O(logn) ，这段代码循环 n 次，时间复杂度就是 O(nlogn) 了。...那么，最好的情况是如果数组中第一个元素正好是要查找的变量 x ，时间复杂度就是 O(1)。最坏的情况是遍历了整个数组都没有找到想要的 x，那么时间复杂就成了 O(n)。...比如下面这段代码中，首先 int i= 0; 申请一个空间存储变量，是常量可以忽略，int[] a = new int[n]; 申请了一个大小为 n 的 int 类型数组，剩下的代码都没有占用更多的空间

4352 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭