时间复杂度O(n)是如何工作的
时间复杂度是衡量算法执行时间随输入规模增加而增加的程度的度量。其中，O(n)表示算法的时间复杂度为线性复杂度，即随着输入规模的增加，算法的执行时间呈线性增长。
在时间复杂度为O(n)的算法中，算法的执行时间与输入规模n成正比。换句话说，如果输入规模n增加一倍，算法的执行时间也会增加一倍。这是因为算法在执行过程中需要遍历或处理输入规模n的所有元素一次。
具体来说，时间复杂度为O(n)的算法会按照输入规模n的大小进行n次操作，其中每次操作所花费的时间相对稳定。这样的算法通常是基于循环或迭代的，通过遍历输入数据一次来完成任务。
时间复杂度为O(n)的算法的优势在于其执行时间与输入规模呈线性增长，相对较小的输入规模下，算法执行速度较快。然而，随着输入规模的增加，算法的执行时间也会线性增加，可能在处理大规模数据时效率较低。
应用场景：
- 遍历线性结构：当需要遍历线性数据结构，如数组或链表时，时间复杂度为O(n)的算法非常适用。例如，在一个包含n个元素的数组中查找某个特定元素，就可以通过遍历数组一次来完成。
腾讯云相关产品和产品介绍链接地址：
- 云服务器CVM：https://cloud.tencent.com/product/cvm 云服务器CVM是腾讯云提供的一种可弹性伸缩的云主机服务，可以根据业务需求自由调整配置和规模。
- 云数据库MySQL：https://cloud.tencent.com/product/cdb_mysql 云数据库MySQL是腾讯云提供的一种高性能、可扩展的云端关系型数据库服务，适用于各类在线应用和网站。
- 云函数SCF：https://cloud.tencent.com/product/scf 云函数SCF是腾讯云提供的事件驱动的无服务器计算服务，可实现按需运行函数代码，无需管理服务器。
请注意，以上仅为腾讯云的一些相关产品和介绍链接，其他云计算品牌商的类似产品也可供选择。
相关·内容
1回答
下面我附上了一个代码块。请告诉我下面的代码是如何有O(n)时间运行时间的。
def _height2(self, p):
if self.is_leaf(p):
return 0
else:
return 1 + max(self._height2(c) for c in self.children(p))
我不明白它在O(n)时间复杂度中是如何工作的。请帮我学一下。
浏览 4提问于2020-09-14得票数 0
回答已采纳
1回答
我在思考如何正确计算这个函数的时间复杂度：
def foo(lst):
jump = 1
total = 0
while jump < len(lst):
for i in range(0, len(lst), jump):
total += i
jump = jump * 2
return total
我假设它是O(n)，其中n是列表的长度。
我们的while循环是O(n)，for循环也是O(n)，这意味着我们得到了2*O(n)，它等于O(n)。
我说的对吗？
浏览 3提问于2021-01-19得票数 0
我对计算pop和push在数据结构中的成本感到有点困惑。
1)它说，push(x)：像往常一样实现，Θ(1)时间
这是否意味着，如果一个推送操作完成Θ(1)次，如果完成两个操作，Θ(2)时间，以及如果n个推送操作完成Θ(n)次？
2) multipop(k)：调用pop()最多k次，Θ(k)最坏情况时间
这就像从堆栈S中删除k个顶部对象一样。Θ(k)是怎么来的？由于弹出了k个对象，因此时间将为Θ(k)。
3)这是最令人困惑的部分。从空开始，执行m次操作。总时间是多少？
至多m次推送，m次弹出: total O(m)。这是如何得到O(m)的。既然有2m次运算，难道不需要是O(2m)吗？
因此，在
浏览 3提问于2016-11-21得票数 0
2回答
排序依据:二进制搜索树
、、、
我对最坏情况时间和平均情况时间复杂性感到有点困惑。我的困惑来源是
我的目标是按升序缩短数据:我选择BST来完成我的sorting.Here任务，我正在做的打印数据的工作是按升序进行的。
1) Construct a binary search tree for given input.
Time complexity: Avg Case O(log n)
Worst Case O(H) {H is height of tree, here we can Assume Height is equal to number of n
浏览 1提问于2012-05-22得票数 1
回答已采纳
我看到了这个解释，但我仍然不能完全理解它。如果我们遵循这样的逻辑:假设某个算法在O(n)时间内工作，那么:让我们假设n= 1000 (4位长)，那么时间复杂度T(n) = O(8)让输入的大小加倍。时间是指数增长的，所以O(n)不是多项式时间？
浏览 7提问于2021-06-02得票数 0
3回答
我有这样的代码，它以排序的顺序返回数组的平方，并试图确定它的时间复杂性。我在数据(O(n))中执行一个循环，然后使用合并排序(O(n log n))。我认为这意味着我在做n * n log n工作，所以这是n^2的复杂性。但是当我检查这个问题的答案时，这个函数的时间复杂度显然只是n log n。为什么会这样呢？
public int[] sortedSquares(int[] A) {
for(int i = 0; i < A.length; i++) {
A[i] = A[i] * A[i];
}
mergeSort(A);
浏览 4提问于2020-06-24得票数 0
回答已采纳
1回答
static void flip(int [] list, int start, int end){
if(end - start > 0){
flip(list, start + 1, end - 1);
swap(list, end, start);
}
}
这里，交换方法的时间复杂度是O(1)。整个翻转函数O(n)或O(log )的时间复杂性吗？如果两者兼而有之，你如何分析？
浏览 1提问于2022-03-17得票数 0
1回答
我有3种算法(A1、A2和A3)，它们的估计时间复杂度分别为O(n Log n)、O(K n)和O(Q n)，其中K和Q是不同的动作参数。然后，我有第四种算法，它连续运行这3种算法(每种算法都需要前一种算法的结果)。
我对该如何估计算法套件的总复杂性感到困惑。据我所知，O(n Log n)比O(K n)和O(Q n)增长得更快，因此在时间消耗方面最重要的部分将是A1，这可能是足够大的n最相关的行为。但这并不能反映出，即使在A1完成之后，A2和A3仍然需要很长的时间。
所以我在想，我该怎么解释呢？仅仅说复杂性是O(n Log n)就足够了吗？
浏览 0提问于2017-05-05得票数 3
回答已采纳
3回答
学习算法，当涉及到计算时间复杂度时，我有点困惑。据我所知，如果算法的输出不取决于输入大小，则需要恒定的时间，即O(1)。而当它依赖于输入时，它被称为线性时间，即O(n)。
然而，当我们知道输入的大小时，时间复杂度是如何计算出来的呢？
例如，我有下面的代码，它输出1到100之间的所有素数。在这个场景中，我知道输入(100)的大小，那么这将如何转化为时间复杂性？
public void findPrime(){
for(int i = 2; i <=100; i++){
boolean isPrime = true;
for(int j = 2; j
浏览 8提问于2020-06-04得票数 3
回答已采纳
1回答
请检查下面的时间复杂性是否正确。
循环1
for(int i =0; i*i < n; i+=2)
我认为在这个循环中所做的工作将是O( sqrt(n) )，因为我知道当我到达sqrt(N)时将满足这个条件。而且，递增器(i +=2)将导致结果在n/2中完成，因此完成的总体工作将是sqrt(n)/2。
循环2
for(int i =0; i*i < n; i*=2)
我认为这个循环中完成的工作将是O( log(n) )，因为与前面的问题不同的是增量器(i*=2)，它将导致循环在log(N)次中运行。因此，总体工作变成了log(sqrt(n))，成为O(log(n))
PS:如果有人
浏览 1提问于2021-03-16得票数 1
回答已采纳
2回答
例如，如果我在我的方法中有两个参数M和N，并且时间复杂度被证明是O(M+N)，为什么人们说O(M+N)而不是O(N)，O(N)是O(2N)的简化形式？什么时候我们应该在大O符号中使用多个变量？这背后有什么道理吗？传递给参数的不同变量将如何影响增长率，为什么不将它们组合成一个大O变量？我想不出哪一个实例中传入的不同变量参数会影响运行时。我刚开始接触数据结构和算法，所以我想知道。
浏览 1提问于2020-07-02得票数 1
1回答
数组中顶k频繁元素的时空复杂性
、、、、
对于给定问题的时间和空间复杂性，存在着一种小小的混淆：
给定一个大小为N的数组，返回顶级K频繁元素的列表。
基于最流行的解决方案：
使用大小为HashMap的K，并将每个条目的计数作为值。
通过遍历上面生成的MaxHeap，构建大小为K的HashMap。
将MaxHeap中的元素弹出到列表中并返回列表。
K是输入中唯一元素的数目。
空间和时间复杂度为: O(K)和O(K*log(K) )。
现在混乱就从这里开始。我们知道，在上述分析中，我们正在处理最坏的情况。所以，当数组中的所有元素都是唯一的时，K的最坏值是N。
因此K <= N.因此O(K)被表示为O(N) ??
浏览 3提问于2019-05-19得票数 0
回答已采纳
1回答
以下代码的时间复杂度是多少？
def func(n):
for _ in range(n):
if n == 4:
for _ in range(n):
<do something>
对于一个特定的输入(n = 4)，它将只是O(n^2)，但对于所有其他输入，它将是O(n)。在这种情况下，最坏的情况显然是O(n^2)，但我的讲师说O(n)是正确的答案。如果"big-Oh“符号表示的是最坏的情况，为什么它不是O(n^2)？
另一个是：
def func2(n):
for _ in rang
浏览 0提问于2014-04-01得票数 1
1回答
设A，B和C是n个整数的三个数组。我想找出3个整数a，b，cs.t。A属于A，b属于B，c属于C和c=a+b。
方法：
计算所有可能的和a+b并将其存储在哈希映射中。时间复杂度=O(n^2)通过数组C进行分析，并检查散列映射中是否存在元素。
这种方法需要O(n^2)空间和O(n^2)时间复杂度。在没有额外空间(即空间复杂度= O(1))的情况下，它能在O(n^2)时间内找到a，b，c吗？
浏览 5提问于2020-09-23得票数 2
1回答
我如何找到作为问题大小n的函数的时间复杂度？
sum = 0;
if (EVEN(n)) {
for (i = 0; i < n; i++) {
if (i % 2 == 0) {
O(logn)
}
else {
sum++;
}
}
}
else {
sum = sum + n;
}
浏览 3提问于2015-10-08得票数 0
4回答
假设我有一个矩阵，它有X行和Y列。元素的总数是X*Y，对吗？那么，这就是n=X*Y吗？
for (i=0; i<X; i++)
{
for (j=0; j<Y; j++)
{
print(matrix[i][j]);
}
}
那么这不是意味着这个嵌套的for循环是O(n)吗？或者我误解了时间复杂性是如何工作的？
通常，我认为所有嵌套的for循环都是O( n ^2)，但是如果它通过X*Y调用print()，这不是意味着时间复杂度是O( X*Y )并且X*Y等于n吗？
浏览 1提问于2012-04-27得票数 3
回答已采纳
2回答
我需要帮助的问题是：
for (int i = 0; i < n*n; i++)
for (int j = 0; j < n*n; j++)
if (i == j)
for(int k = 0; k < n; k++)
sum++;
我理解i和j循环是如何O(n^4)的。但是，从if语句开始，我不知道剩余代码片段的大O是什么。如果我在课堂上正确地复制了答案，O(n^4)就是整个代码片段的运行时间。因此，从if开始的运行时间似乎可以忽略不计。尽管如此，我仍然想了解它是什么，以及为什么我认为答案是O(
浏览 0提问于2018-04-29得票数 1
回答已采纳
我试图了解是否有任何替代蛮力算法(或轻微的改进/最坏的性能比幼稚的蛮力算法)仍然将导致O(N^2)的时间复杂性和O(1)辅助空间。
这是我的蛮力伪码：
procedure distinct(Input: array)
for i=0 to i < length of array
for j=i+1 to j < length of array
if array[i] ==
浏览 1提问于2016-03-07得票数 1
回答已采纳
这个问题已经出现在我的算法课上了。我的想法是：
我认为答案是否定的，具有O(n)的最坏时间复杂度的算法并不总是比O(n^2)的最坏时间复杂度的算法更快。
例如，假设我们有总时间函数S(n) = 99999999n和T(n) = n^2，那么很明显，S(n) = O(n)和T(n) = O(n^2)，但对于n< 99999999，T(n)比S(n)更快。
这样的推理有效吗？我有点怀疑，虽然这是一个反例，但它可能是错误想法的反例。
非常感谢！
浏览 5提问于2016-06-15得票数 3
回答已采纳
为什么ArrayList add()和add( index，E)复杂度是摊销常数时间？
为什么O(1)用于单add()操作，O (n )用于单add(int index，E)操作，O(n)用于添加n个元素(n add操作)？假设我们很少使用add ( index，E)添加到数组末端？
数组(和ArrayList)的操作复杂性不是已经有n个元素的：
加()- O(1)？
添加(int索引，E) - O(n)？
如果我们做了一百万次插入，平均1和2不可能是O(1)，对吗？
甲骨文为什么说
添加操作运行在分期常数时间中，即添加n个元素需要O(n)时间。
I认为复杂性对于add
浏览 17提问于2017-07-20得票数 22
回答已采纳
当我被介绍给一个算法时，我知道如何找到算法的时间复杂度，但当我得到算法执行的次数和所用的时间时，我似乎不知道如何计算出算法的时间复杂度。
当O(n)，O(n)或O(n^2)这样显而易见的东西时，我有时可以得到它，但以这个问题为例：
算法运行大小为n的给定输入。如果n为4096，则运行时间为512毫秒。如果n为16384，则运行时间为1024ms。如果n为36864，则运行时间为1536毫秒。
时间复杂度是多少？
我认为它是n* 2，t* 1.5，但我不太确定如何计算它。
感谢您的帮助:)
浏览 3提问于2012-10-14得票数 0
回答已采纳
正常情况下，构建rb-tree需要O(N*log(N))时间。
然而，。
这是如何工作的呢？初始化前是否有排序检查？还是从最右边的搜索？
浏览 0提问于2021-02-19得票数 0
很多次我都听说过，如果我们可以在多项式时间把问题A简化成问题B，那么问题B至少和问题A一样难。这个陈述有多精确？我认为我们应该这样理解:如果A可以被多时间缩减为B，那么如果B有一个多时间算法，那么它必须存在于A。
我的观点是，与B(n^4)相比，A实际上比B(可能具有更高的时间复杂度，例如O(n^100) )更难，因为多时间缩减本身是耗时的。因此，O(n^4)和约化所需的时间可以给出A的一个算法，即O(n^100)。所以每次我读A并不比B难，在这种情况下，A不可能没有多项式时间算法，而B有一个多项式时间算法。对吗？
浏览 5提问于2015-02-01得票数 4
回答已采纳
1回答
我想验证解决leetcode上的问题的空间和时间复杂性。由于叠加空间的影响，空间复杂度为O(N)。时间复杂度为O(2^N)，因为每个ith级别上的工作是将2^i元素添加到列表中。因此，将2^i从0到N相加得到O(2^N)。我说的对吗？我不确定，因为这三个官方解决方案的时间复杂度O(N*2^N)。
import java.util.ArrayList;
import java.util.List;
public class Solution {
// Space Complexity: O(N)
// Time Complexity: 2^0 + 2^1 + ... + 2^
浏览 2提问于2022-05-26得票数 0
回答已采纳
1回答
算法的时间复杂度
、、、、
嗨，我一直在研究和尝试学习hw来检查某些算法的时间复杂性。
话虽如此，我还是不知道，并开始尝试计算出某些算法的精算化案例和一般情况。
程序#1:这是一个用RPN格式计算的计算器.
function evaluate() {
var input = prompt("Please enter your input string\n\nExamples of input strings:\n\n\t1. 10 4 5 + *\n\t2. 10 4 5 + * 2 +\n\t3. 10 8 *");
var values = input.split(&#
浏览 0提问于2018-05-08得票数 0
1回答
根据的说法，如果所有的点都已经排序，那么安德鲁的算法将在线性时间内运行。我们将以排序点为例。
然而，在伪代码中，它说：
for i = 1, 2, ..., n:
while L contains at least two points and the sequence of last two points
of L and the point P[i] does not make a counter-clockwise turn:
remove the last point from L
append P[i] to L
现在，我们可以看到一个for循环和一个嵌套在f
浏览 1提问于2015-06-09得票数 2
回答已采纳
我理解如何：
for (int i=0; i<n; i++)
这个时间复杂度是O(n)。
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
for (k=0; k<n; k++)
这是O(n^3)，对吗？
i=1
do
//......
i++
while (i*2 <n)
是O(n)吗？还是说它就是O(n/2)
浏览 0提问于2013-03-23得票数 3
2回答
void f(int n)
{
doOh(n);
if(n<1) return;
for(int i=0; i<2; i++)
{
f(n/2);
}
}
doOh(n)的时间复杂度为O(N)。如何计算给定函数的时间复杂度？
浏览 0提问于2021-11-27得票数 0
2回答
我试图理解Big-O表示法，所以我使用while循环制作了自己的O(n)示例，因为我发现while循环在Big O表示法中理解起来有点混乱。我定义了一个名为linear_example的函数，它接受一个列表，例如is python：
所以我的代码是：
def linear_example (l):
n =10
while n>1:
n -= 1
for i in l:
print(i)
我的想法是for循环中的代码以O(1)的恒定时间运行，而while循环中的代码以O(n)时间运行。因此，它的结果是O(1)+O(n)
浏览 0提问于2018-05-03得票数 0
2回答
我知道第一个循环是O(n)，因为第二个是嵌套循环，所以它将是O(n *东西)。我知道嵌套循环将迭代n次，并且每次递减。但是如何确定它的时间复杂性呢？ int a = 0;
for (i = 0; i < N; i++) {
for (j = N; j > i; j--) {
a = a + i + j;
}
}
浏览 21提问于2021-07-14得票数 1
回答已采纳
2回答
以下代码的时间复杂度是多少？
a = 2;
while (a <= n)
{
for (k=1; k <= n; k++)
{
b = n;
while (b > 1)
b = b / 2;
}
a = a * a * a;
}
--我在和外循环做斗争，，也就是loglogn，我不明白为什么。如果最后一行是a = a * a * a * a;，时间复杂度会发生什么变化？
for循环是O(n)，内部循环是O(logn)。
所以总的来说，O(n*logn*loglogn)
浏览 4提问于2016-09-10得票数 1
回答已采纳
2回答
假设我们的任务是将字符串中的单词颠倒过来。
所以如果我们有：
玛丽吃了一只小羊羔
我们会得到：
yram dah a elttil bmal
实现的算法如下：
string wordsToSplit = "Mary had a little lamb";
string[] words = wordsToSplit.split(" ");
string wordsReversed = "";
foreach( string word in words )
{
string reversedWord = "";
浏览 1提问于2014-11-21得票数 0
1回答
假设isSubstring在O(N+M)时间运行，则该通用代码在O(N)时间内运行。我们如何从这得到O(N)时间复杂度？
public static boolean isRotation(String s1, String s2) {
int len = s1.length();
if (len == s2.length() && len > 0) {
String s1s1 = s1 + s1;
return isSubstring(s1s1, s2);
}
浏览 8提问于2022-04-01得票数 2
我在网上找到了这个example problem，我就是不明白作者是如何得出这个结论的。 sum1 = 0;
for(k=1; k<=n; k*=2) // Do log n times
for (j=1; j<=n; j++) // Do n times
sum1++;`
sum2 = 0;
for (k=1; k<=n; k*=2) // Do log n times
for (j=1; j<=k; j++) // Do k times
sum2++; 我知道第一个循环的运行时间是O( n ) = nlog(n
浏览 20提问于2020-12-16得票数 0
1回答
关于快速分类杀手
、、
你们中的一些人可能偶然发现了这篇可爱的文章-- \
真正有趣的是，他如何修正快速排序以在O(N log N)中针对已定义的对手执行。
快速排序可能会选择中间元素作为每个步骤的枢轴，因此总是将输入序列完美地分成两半。在O(N)运行时间内可以确定地找到中值，因此总运行时间总是O(N log )。
我的问题是，线性时间中值查找算法不会使用相同的比较函数，在O(N^2)而不是O(N)中执行吗？
编辑：
准确地说:我在质疑基于分区的中值选择算法的复杂性，该算法使用类似于快速排序的策略，它将使用与快速排序相同的比较函数。它如何在O(N)中与这个对手一起工作？
浏览 1提问于2010-11-28得票数 5
回答已采纳
i=2;
while(i<n) {
i = i*i;
//O(1) complexity here
}
我对时间的复杂性很陌生，我想弄清楚这会是什么。我知道，如果迭代是i=2*i，那么它将是O(log(n))，但我不知道如何计算i^2的迭代。
直觉上也是O(log(n))，因为它“迭代速度更快”，但我不知道如何正式解释这一点。
如能提供任何帮助，将不胜感激。
浏览 1提问于2022-08-05得票数 1
1回答
对于一个算法的平均时间复杂度，您使用了什么符号？在我看来，正确的方法是使用大θ来引用一组结果(即使特定的尝试可能不同)。例如，平均数组搜索将是n+1(Θ)/2。
是这样的吗？
对平均搜索时间的解释是/2:在n个第一个整数的访问时间和为n(n+1)/2的情况下，大量随机访问数组的平均时间为(n (n+1)/2 )/n =(n+1)/2，在这种情况下，我认为Θ(n+1)/2将是平均访问时间。这(对我来说)很有意义，但由于我对渐近符号(以及一般的编程)还不熟悉，我想知道这是否是一种常见的做法。
我之所以问这个问题，是因为我很困惑地发现，在像http://bigocheatsheet.com这样的页面
浏览 0提问于2013-05-11得票数 1
回答已采纳
1回答
基于我的研究，我得到了关于这个简单算法的相互矛盾的信息。该算法是一个基本的矩阵变换，它是一个n×n矩阵A的换位算法。
我目前的理解是，该算法将在O(n^2)时间运行，空间复杂度为O(1)，因为我们操作的矩阵与我们处理的矩阵相同。
但是-我也被告知它实际上会运行O(n)时间，并且具有O(n)的空间复杂性。这意味着它不会到位，因为它需要额外的空间来操作。
对于下面的转位来说，哪个思维过程是正确的？
Transpose(A)
1. for i = 1 to n -1
2. for j = i + 1 to n
3. exchange A[i, j] with A[j
浏览 4提问于2022-02-15得票数 1
回答已采纳
1回答
我设计了一个算法，将10的幂转换为二进制，假设n是2的幂。我使用高斯方法来利用这个很好的方法的快速运行时间。为此，我将n除以2，并将其发送到Gauess方法，如下所示：
changetoBinary(n)
if n=1
return binary of 10 which is 1010
else
return gauess(n/2,n/2)
很明显，猜测方法将首先分裂，然后征服，然后合并。最后，我们将数字更改为二进制。现在我的问题是关于算法的运行时间:我的理解是，由于猜测运行时间是θ(n^log3(Base2))，我们可以说这个算法的运行时间也是相同的，因为大多数工作都是由Gue
浏览 0提问于2014-02-21得票数 1
1回答
同时循环的时间复杂度
、、、、
我一点也不确定我是否理解时间复杂性的计算。我被赋予了这些循环，这是我的计算。然而，我一点也不确定关于这里的大O应该说些什么。
循环1：
lst = []
i=1
while i<n:
lst = list(range(i))
i *= 2
我假设每个操作都需要O(1)时间。在此循环中，第1行和第2行各执行1次。while循环的第一行有3个操作-范围、列表和将该值赋值给lst。因为我们在处理range，所以我假设它运行n+1时间。
循环的最后一行有两个操作:乘2和将该值赋值给i，它
浏览 2提问于2013-11-23得票数 3
2回答
渐近分析问题
、、、
我在geeksforgeeks.org上发现了几个我似乎无法理解的问题(#1和#3)。我希望有人能帮我弄清楚答案：
澄清true/valid或false
1. QuickSort的时间复杂度为Θ(n^2)
我的回答是正确的，但它是错误的，为什么？如果快速排序的时间复杂度为O(n^2)，并且我们知道快速排序(g(N))={ f(n)，其中c1*g(n) <= f(N) <=c2*g(n)和n >= n0}，那么这不是证明它是真的吗，因为c2*g(n)作为上界可以等于f(n)？
2. QuickSort的时间复杂度为O(n^2) -真
3.所有计算机算法的时间复杂度可以写成Ω(1
浏览 1提问于2014-01-23得票数 3
我手头有问题，可以通过以下两种方式解决。
if(...) //First if statement
for( i = 0; i < n; i++ ) //Loop over n elements
{ ... } //Some statement; Time Complexity O(1)
if(...) //Second if statement
for( i = 0; i < n; i++ ) //Loop over n elements
{ ... } //Some statement; Time Complexity
浏览 2提问于2016-01-18得票数 1
2回答
def f1(n):
for i in range(n):
k = aux1(n - i)
while k > 0:
print(i*k)
k //= 2
def aux1(m):
jj = 0
for j in range(m):
jj += j
return m
我正在试图计算函数f1的时间复杂度，但它并不适用于我。
如果对我的工作有任何反馈意见，我将不胜感激。
我正在做的事情:我首先尝试替代i=1并尝试进行迭代，因此函数用m=n-1调用aux，aux1迭代n-1时间并返回m = n-1，
浏览 1提问于2021-02-20得票数 0
回答已采纳
1回答
时间复杂度和实验结果
、、、
我有两个算法A和B，它们工作在逻辑图上，我想从时间上比较它们的效率。
当我计算这两种算法的时间复杂度时，我发现：
Time Complexity of A: O(2*n*n)
Time Complexity of B: O((n*n)/2)
根据维基百科的说法，当我们计算时间复杂度时，我们忽略了系数，这产生了：
Time Complexity of A: O(n^2)
Time Complexity of B: O(n^2)
我做的第二步是通过实验计算每个算法对不同大小的图所需的时间。下面，x轴表示图形中的节点数，y轴是以秒为单位的时间。
正如您所看到的，这两种算法在处理大型图时有很
浏览 4提问于2013-06-05得票数 3
回答已采纳
1回答
如果一个算法最坏的运行时间是6n^4 + 2，其最佳运行时间是67+ 6n^3，那么最合适的渐近表示法是什么？
我在试着学习大O符号。
是Θ(n^2)吗？
浏览 1提问于2022-02-02得票数 -1
回答已采纳
我听说heapq.merge函数是专门用来合并2个有序数组的？时间复杂度是O(n)吗？如果不是，它是什么?为什么？还有它的空间复杂性是什么。 我正在解决用两个指针合并两个排序数组的问题，并且可以达到O(n)时间复杂度和O(n)空间复杂度。
浏览 51提问于2019-02-18得票数 5
在下面的四个选项中，难道不是3，即O(n平方)应该是最糟糕的时间复杂度吗？因为运行需要更多的时间，而日志(N)运行的时间更短吗？但不幸的是，给出的答案是备选案文4。
我的逻辑怎么了？
O(log(n!))O(n)O(n²)O(log(log(n)))
浏览 5提问于2022-05-25得票数 -2
我是一个初级开发人员，仍然不是很熟悉大O。
这是我的leetcode问题的解决方案，我不确定这个解决方案的时间和空间复杂度是多少。
String s = "";
String t = "";
int back = 0;
for (int i = S.length() - 1; i >= 0; i--) {
if (S.charAt(i) == '#') {
back++;
continue;
}
if (back
浏览 3提问于2019-11-28得票数 0
2回答
算法A对存储n个元素的数组执行时间复杂度为O(log )的运算。
算法B从数组中选择log个元素，并对每个元素执行O(n)计算。
由于d(n) = O(f(n))和e(n) = O(g(n))，那么d(n)*e(n) = O(f(n)*g(n))，这是否意味着算法A和B的时间复杂度都是O( n )？
浏览 0提问于2018-11-11得票数 0
如果一些机器学习算法的时间复杂度可以定义为O(N*P)，其中N是行数，P是特征大小，那么kNN和朴素贝叶斯等机器学习算法的时间复杂度是多少？ O(N*P)时间复杂度是否与O(N)属于同一类别，因此它是“线性复杂度”吗？如果P=N是真的，那么它不能也被算作O(N^2)，因此是二次复杂度吗？那么，我们到底可以称之为什么复杂性，它是不是还没有确定呢？谢谢。
浏览 29提问于2020-12-28得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
