当函数中含有单元时，如何求其渐近复杂度？(2^(2^ceil(log2(N)= O( 2^n )？
在计算函数的渐近复杂度时，如果函数中含有单元（循环、递归等），可以通过以下步骤来求解：
- 首先，确定函数中含有单元的部分，即需要进行复杂度分析的部分。
- 然后，确定单元的执行次数与输入规模之间的关系。这可以通过观察代码逻辑、循环结构、递归调用等来确定。
- 接下来，将单元的执行次数表示为一个函数，记作T(n)，其中n表示输入规模。
- 根据T(n)的定义，可以使用递归关系式或迭代关系式来表示T(n)与T(n-1)、T(n/2)等之间的关系。
- 最后，根据递归关系式或迭代关系式，使用数学归纳法或迭代法求解T(n)的渐近复杂度。
对于给定的函数中含有单元的情况，如题目中的函数，可以按照上述步骤进行求解。具体步骤如下：
- 首先，观察函数中的单元部分，即2^(2^ceil(log2(N))。
- 然后，确定单元的执行次数与输入规模N之间的关系。根据观察，可以发现单元的执行次数是指数级增长的，即随着N的增大，执行次数呈指数倍增长。
- 接下来，将单元的执行次数表示为一个函数T(N)。在这个例子中，T(N) = 2^(2^ceil(log2(N)))。
- 根据T(N)的定义，可以使用递归关系式来表示T(N)与T(N-1)之间的关系。在这个例子中，T(N) = 2^(2^ceil(log2(N))) = 2^(2^ceil(log2(N-1))) * 2^(2^ceil(log2(N-1)))。
- 最后，根据递归关系式，可以使用数学归纳法来求解T(N)的渐近复杂度。根据观察，可以发现T(N)的渐近复杂度为O(2^N)。
综上所述，当函数中含有单元时，如题目中的函数，可以通过观察单元的执行次数与输入规模之间的关系，并使用递归关系式和数学归纳法来求解其渐近复杂度。对于这个函数，其渐近复杂度为O(2^N)。
关于腾讯云相关产品和产品介绍链接地址，由于要求不能提及具体的云计算品牌商，无法给出具体的推荐产品和链接地址。但腾讯云作为一家知名的云计算服务提供商，提供了丰富的云计算产品和解决方案，可以根据具体需求在腾讯云官网上查找相关产品和介绍。
相关·内容
1回答
// Assume n is some random integer
int q = 1;
while (q <= Math.Sqrt(n))
{
q++;
int k = 1;
while (k <= Math.Log(n, 2))
{
k++;
if (q^k == n){
return true;
}
}
return false;
在上面的代码中，我发现很难决定最坏情况下的大O是什么。由于循环运行N次，其中嵌套循环运行log2(N)次，我知道它应该是O(sqrt(n)*log2(n))次。然而，我
浏览 0提问于2020-09-02得票数 0
下面的问题是最近在大学里的一项任务。我原以为答案是n^2+T(n-1)，因为我认为n^2会使它的渐近时间复杂度O(n^2)。与T(n/2)+1一样，其渐近时间复杂度为O(log2(n))。
答案被返回，结果正确的答案是T(n/2)+1，但是我无法理解为什么会这样。
有人能解释一下为什么这是这个算法最糟糕的时间复杂度吗？很可能我对时间复杂性的理解是错误的。
浏览 1提问于2016-04-14得票数 4
回答已采纳
def dividing(n):
while n!=1:
n=math.floor(n/2)
return True
有这段代码，我最初的想法是，它的复杂度只是n，因为它只是输入，没有方格，除了研究n/2时，我发现它的大O复杂度是Log(m)，所以我现在很困惑，这个大o复杂度是log(m)吗？若然，为甚麽会这样呢？
浏览 7提问于2021-03-29得票数 2
回答已采纳
我不了解渐近分析，在试图找到大O表示法的同时，在一些问题中，它被作为log给出，用于级数的相同简化，而对于另一个问题，则以n形式给出。
以下是问题：
int fun(int n)
{
int count = 0;
for (int i= n; i> 0; i/=2)
for (int j = 0; j < i; j++)
count ++;
return count;
}
T(n)=O(n)
int fun2(int n)
{
int count = 0;
for(i = 1; i < n;
浏览 4提问于2020-01-13得票数 0
我运行了一个程序来找出n+1和2**ceil(log2(n+1))之间的差，其中n是2的幂。它一直呈指数级增长。
所以从大O的定义来看，没有常数c‘使得-
2^(2^ceil(log2(n))) <= c' * 2^n
因此
(2^(2^ceil(log2(n)))) != O( 2^n )
上面的说法正确吗？如果是，那我怎么证明呢？
浏览 28提问于2017-01-24得票数 0
回答已采纳
如果求f(n)是θ(N)
i = 1;
sum = 0;
while (i <= n)
do if (f(i) > k)
then sum += f(i);
i = 2*i;
它的运行时间是O(n^3)，因为函数可能被调用了n次，还是它是O(n)？或者是关于θ的东西，因为这是我们所知道的信息？我对此非常迷茫.
浏览 2提问于2016-09-27得票数 0
回答已采纳
4回答
我刚接触过Java，我的问题是关于大O复杂性的。
对于a)，它显然是嵌套循环的O(n^2)。
for ( int i = 0; i < n; i++)
for ( int j=0; j < n; j++ )
但是，对于b)，随着sum++操作的结束，以及嵌套循环的复杂性，这是否改变了它的大O复杂度呢？
int sum = 0;
for ( int i = 1; i <= n; i++)
for ( int j = n; j > 0; j /= 2)
sum++;
浏览 1提问于2015-05-13得票数 5
回答已采纳
1回答
3嵌套循环复杂度
、、、
int x = 0;
for (int i = n; i >= 3; i--) {
for (int j = 1; j <= Math.log(i) / Math.log(2); j++) {
for (int t = 0; t <= n; t += j) {
x++;
}
}
}
System.out.println(x);
正如您所看到的，我有3个for循环，它们的条件相互依赖。
我的分析：
第一个循环：我假设它将运行(n-2)多次“最坏情况”场景。
第二个循环：我假设它将运行log(n)多次
浏览 0提问于2019-03-20得票数 2
回答已采纳
p = 0
for( i=1; i<n; i=i*2 ) {
p++ // log n
}
for( j=1; j<p; j=j*2 ) {
some_statement // log P
}
// O( log log n )
为什么来自独立循环的变量会影响另一个循环的时间？如果我们要删除第二个循环，时间复杂度将仅仅是O(logn)，这要慢得多。为什么时间复杂度不只是logn + logn =2 logn，因此O(logn)？
浏览 6提问于2022-09-29得票数 2
回答已采纳
3回答
大-O小澄清
、、
当涉及到时间复杂性时，O(log(log(n)))实际上只是O(log(n))吗？
您同意这个函数g()的时间复杂度为O(log(log(n)))吗？
int f(int n) {
if (n <= 1)
return 0;
return f(n/2) + 1;
}
int g(int n) {
int m = f(f(n));
int i;
int x = 0;
for (i = 0; i < m; i++) {
x += i * i;
}
return m;
}
浏览 5提问于2016-02-15得票数 20
回答已采纳
1回答
嵌套循环的时间复杂度
、、、、
下面这个代码块的时间复杂度是多少？
我的尝试是，最外层的循环运行n/2次，内部的循环运行2^q次。然后将2^q与n相等，得到Q为1/ 2 (log n)与基2相乘，得到O(nlog(n))的时间复杂度，得到的解为O(nlog^2(n))。
void function(int n) {
int count = 0;
for (int i=n/2; i<=n; i++)
for (int j=1; j<=n; j = 2 * j)
for (int k=1; k<=n; k = k * 2)
浏览 0提问于2018-12-18得票数 4
回答已采纳
1回答
这个函数的复杂度是O(nlogn)吗？
find(n){
for(i=0; i<=n-1; i++){
for(j=1; j<=i; j=j*2)
print("*");
}
}
浏览 0提问于2020-03-07得票数 0
1回答
我正在处理一个问题，在这个问题中，我需要对数据的80GB进行排序。我只有1GB主内存来对数据进行排序。显然，我们将在这里应用外部排序方法。但我的问题是哪种k-合并排序会更有效？
8路合并后10路合并
5路合并后16路合并
K-合并排序的复杂性是O(nk^2)，其中n是元素数.假设我使用此方法计算复杂性：
8路合并，然后是10路合并
8 way merge - O(n*8^2) => O(64n)
10 way merge - O(8n*10^2) => O(800n)
Total time complexity => O(64n) + O(800n)
5路合
浏览 1提问于2015-12-07得票数 0
回答已采纳
因此，这些是我必须找到的时间复杂度的for循环，但我不太清楚如何计算。
for (int i = n; i > 1; i /= 3) {
for (int j = 0; j < n; j += 2) {
... ...
}
for (int k = 2; k < n; k = (k * k) {
...
}
对于第一行，(int = n；i> 1；i /= 3)，继续以3为跳转，如果我小于1，循环就在那里停止，对吗？
但它的时间复杂性有多大呢？我想是的，但我不太确定。我认为它是n的原因是，如果我假设n是30
浏览 0提问于2018-03-15得票数 0
回答已采纳
3回答
我有以下迭代平方的实现：
def power(a, b):
result = 1
while b > 0:
if b % 2 == 1:
result = mult(result, a)
a = mult(a, a)
b = b // 2
return result
mult()方法乘以2个给定的数，当一个是x比特的长度，另一个是y位的长度时，乘法所需的运算数是x*y+(x+y)运算，这在复杂性分析中需要考虑。
当a是n位长，b是m位长时，我试图找到一个O()表示法界，当a是n位长，b是m位长时，作为n和m函数完成的广义运算数的界。我只需要
浏览 0提问于2018-04-28得票数 2
回答已采纳
1回答
在计算以下片段中的时间复杂性时，我有一个疑问。
例1:- for (i = n；i>=1；i=i/2) printf("%d"，i)；
例2:- for (i = 1；i< n；i=i*2) printf("%d"，i)
我能告诉您，上面的代码是否需要O(N/2)或O(log )时间复杂度来运行输入？
提前谢谢。
浏览 1提问于2016-04-04得票数 0
回答已采纳
1回答
以下递归函数的时间复杂度是多少？
int DoSomething(int n){
if(n<=2)
return 1;
else
return (DoSomething(floor(sqrt( n) )) + n);
}
备选方案如下：-
O(n^2)
O(n log n) //所有日志均以2为基数
O(原木n)
O(原木n)
浏览 0提问于2017-06-29得票数 0
回答已采纳
i = 1;
while(i<N) {
i*=2;
}
我认为上面代码的时间复杂度是O(N)，但我不确定。你能让我知道你认为它是O(Log )和原因吗？
浏览 0提问于2016-10-16得票数 2
为什么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
回答已采纳
FFT乘法的大O记法是O(nlogn)。下面算法中给出的循环下的FFT乘法的Big-O表示法是什么？代码在matlab中给出，FFTmulti是两个多项式的快速傅立叶变换乘法函数
rG=1;
rN=1;
AreaFunc=[1 2 5 2 3 6 7 2 4 5 6];
N=length(AreaFunc);
for i=1:(N-1)
ref_coeff(i) = (AreaFunc(i+1) - AreaFunc(i)) / (AreaFunc(i+1) + AreaFunc(i));
end
ref_coeff=[ref_coeff rN];
G = (1 + rG) /
浏览 1提问于2013-02-04得票数 0
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
4回答
计算排序的复杂度
、、
sort对元素(- )执行大约N*log2(N) (其中N是距离)比较，所以它的复杂度是N*log2(N)。请帮我计算下一段代码的复杂度：
void func(std::vector<float> & Storage)
{
for(int i = 0; i < Storage.size() - 1; ++i)
{
std::sort(Storage.begin()+i, Storage.end());
Storage[i+1] += Storage[i];
}
}
复杂度= N^2*log2(N)或2log2(2)+3l
浏览 1提问于2013-06-06得票数 2
2回答
与log(n)行为混淆
、、、
s=0;
for(i=1;i<n;i=i*2)
{
for(j=0;j<n;j++)
{
s=s+i*j;
}
s=s+1;
}
我正在尝试建立上述算法的big-o复杂度。外部循环从1开始，运行到n，i中的计数器在每次迭代中加倍，因此这是一个log(n)行为。内部循环从运行到n，具有O(n)行为。我搞不懂它是不是对数O(n*(N))，顺序重要还是不重要？另外，log j从0开始，而不是从1开始，所以这不能是O(n *(N))
浏览 18提问于2018-06-04得票数 3
回答已采纳
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回答
我知道mergeSort函数需要O(logn)，合并函数需要O(n)，因此总复杂度为O(nlogn)。 void mergeSort(int arr[], int l, int r){
if(l >= r){
return;
}
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
} 现在假设我使用相同的逻辑来实现数组元素总和的以下代码 int arraySum(int arr[], int l,
浏览 20提问于2021-02-05得票数 1
回答已采纳
编辑:约束值范围2,1000000000和a<=b
def sqrtoccurrence(a: Int, b: Int): Int = {
val sqrtA = Math.ceil(Math.sqrt(a)).toInt
val sqrtB = Math.floor(Math.sqrt(b)).toInt
if(sqrtA > sqrtB) 0
else 1 + sqrtoccurrence(sqrtA, sqrtB)
}
是O(sqrt(n))还是O(log(n))？我不擅长计算递归运行时
浏览 3提问于2020-01-08得票数 1
回答已采纳
3回答
下面是两个java代码，它们发现整数N中的1位数。
代码1：
int count = 0;
while (N != 0) {
N = N & (N - 1);
count++;
}
return count;
代码2：
int i = N;
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i
浏览 0提问于2016-07-06得票数 0
回答已采纳
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
回答已采纳
对于下面的代码，对于N的巨大值，alloc(realloc)/new操作的复杂性是多少？
据我所知，push_back分配内存：
大小= cst*old_size；
科技委= 2；/代表gcc
因此，我们在k圈内有O(1)，在i圈内有~O(N)。总之，我有O(N)，对吗？
std::vector<int> data;
for (int i = 0; i < N; ++i)
{
for (int k = 0; k < 2 * N; ++k)
data.push_back(k);
for (int k = 0; k <
浏览 1提问于2019-01-30得票数 1
回答已采纳
5回答
以下代码的大O是O(n)还是O(log )？
for (int i = 1; i < n; i*=2)
sum++;
它看起来像O(n)，或者我完全错过了这个？
浏览 1提问于2012-08-20得票数 3
回答已采纳
for ( i = 1; i <= n; i++) {
for ( j = i; j >= 1; j = j / 2) {
// some code
}
}
假设内循环的代码是常数。我以为它是O(n^2)，这是我对这个问题的看法。我认为内循环的运行时间是logi+1，所以我得到了公式：(log1+1)+(log2+1)+...+(logn+1)，然后得到O(n^2)
但是我看到了另一个解决方案是logi，然后答案是O(nlogn)
那我就搞不懂哪一个是对的？我想我是对的但我不确定。所以如果我错了，请说服我为什么第二个是正确的？我知道这两者的区别是内环执行的次数
浏览 7提问于2022-07-20得票数 0
回答已采纳
1回答
我有一个关于复杂性理论的问题。如果我有一个冒泡排序算法，我想找出它的最坏情况运行时间Big O，我们可以得出结论，它是O(n^2)。现在，如果我有一个程序，它执行不同的操作，比如排序算法，搜索算法等，我怎么知道这个程序的最坏情况运行时间(Big O)是多少呢？
例如，在一个程序中使用不同的算法，其各自的最坏情况运行时间Big O符号如何得出整个程序的最坏情况运行时间(Big O)的结论。就像当一个程序有以下内容时: O(n^2)，O(1)，O(n)....这些符号中的哪一个代表了整个程序？
你如何找到这个程序最坏情况下的运行时间Big O？
import java.util.*;
public
浏览 0提问于2014-09-29得票数 0
我在这里读到了投票最多的答案：，但我没有足够的名气来发表评论，所以我不得不发布一个新的问题。
我的问题是:为什么总时间是O(n)？
在寻找斐波那契数的情况下，最坏的情况是检查一个数是否在memo中，可能需要n次，所以整个算法会重复n次，每次都会搜索一次，这需要n次。那么总的时间应该是O(n^2)而不是O(n)。
有人能指出我误解的地方吗？谢谢
浏览 2提问于2018-09-16得票数 1
1回答
人们说这样的话是什么意思：
大O估计可伸缩性。
运行时增长为“输入大小的平方”，考虑到最坏情况下的算法运行在O(n^2).中。
它是否意味着大n 四倍运行时的双输入大小(假设算法运行在O(n^2)中)？
如果您说是，那么假设我们的算法在最坏情况下所采取的步骤数是用以下函数表示的：
因此：
此外，我们可以看到：
但是在这种情况下，我们不能将双倍输入大小的n (即使是n的大值)的运行时增加四倍，因为这样做是错误的。若要查看此图，请查看以下绘图：
这是比率f(2n)/f(n)的图
看起来这一比例并没有趋向于4。
那么，scalabity，是什么呢？“
浏览 2提问于2021-09-22得票数 1
2回答
这是O(N^2)还是O(nlogn)。当有嵌套循环时，不是n^2吗？
int a[], N;
int f1(){ int i, j, sum=0;
for (i=1;; i=2*i)
{
If (i>=N) return sum;
for (j=1; j<2*i;j++) sum+=a[i];
}
浏览 0提问于2019-04-03得票数 2
有人能解释一下为什么这是O(n log n)而不是O(n^2)吗？我的想法是，if语句是n times，else是log n，所以在这两种情况中，最坏的情况是O(n)，所以将它与外部循环O(n)相乘，使之成为O(n^2)，但显然是O(n log n)，我不知道怎么做。
for i in range( len(nums_lst)):
if i < 10:
for k in range( len(nums_lst)):
print(nums_lst[0])
else:
j = 1
while j < len(nums_ls
浏览 7提问于2022-09-28得票数 2
回答已采纳
1回答
对此的明确解释是什么？
O(1)+O(2)+O(3)+O(4)+O(5).......O(n)
这有什么不同？
sigma O(i) 1<=i<=n?
CLRS说它是不同的，但没有解释这些是如何不同的？
浏览 1提问于2014-02-11得票数 0
1回答
在递归过程中，您可以推导出在每次调用此函数时，时间复杂度为：T(n) = 2T(n/2) + O(1)。
递归树的高度是log2(n)，其中是调用的总数(即树中的节点)。
老师说这个函数的时间复杂度是O(n)，但我不明白为什么。
此外，当你把O(n)替换成时间复杂性方程时，会得到一些奇怪的结果。例如,
T(n) <= cn
T(n/2) <= (cn)/2
回到原来的方程式：
T(n) <= cn +1
显然这不是真的，因为cn + 1 !< cn
浏览 3提问于2014-02-17得票数 0
回答已采纳
2回答
二进制到十进制转换的时间复杂度是多少？
我认为如果二进制数中有K位，那么TC将是O(K)，但是，由于我们总是倾向于在二进制数中取N位，那么TC将是O(N)。
我是如何得到这个的，就像我认为一个十进制数将包括多少位数字来表示N位二进制数一样。
然后，10^k-1=2^N-1 => K=N Log2 base10 =>给出了TC = O(N)。
有人能澄清这一点吗？
此外，是否有机会降低这一时间的复杂性？
浏览 4提问于2016-10-11得票数 1
2回答
我有一个函数的伪代码(如下)。
我知道，如果i、j和k中的每一个都是1，那么最糟糕的运行时将是O(n^3)。我很难理解n/2 (如果有的话)对运行时的影响。任何指导都是很好的。
for i=n/2; i < n; increase i by 1
for j=1; j < n/2; increase j by 1
for k = 1; k < n; increase k by k*2
Execute a Statement
浏览 0提问于2018-04-12得票数 0
回答已采纳
我不知道是不是：
O(n)
或
O(5log 10(N)* (n+10)) = O(nlog10n)
或
O(n+k)
我可能错了，但我需要能够计算出来。我真的很困惑。请解释答案，并显示任何计算。谢谢。
浏览 2提问于2020-10-02得票数 0
1回答
我写了一个关于幂集的算法，写成P(a)。正在学习算法的时间复杂性(Big-O)，如果我错了，请纠正我。
算法：
function powerSet(int[] a ){
ArrayList pw = new ArrayList();
pw.add(" ");
for (int i = 1; i <= a.length; i++) //O(n){
ArrayList<String> tmp = new ArrayList<String>();
for (String e : pw)//O(n) {
浏览 3提问于2012-12-27得票数 0
回答已采纳
1回答
算法复杂度渐近图
、、、、
我正在准备一个C++项目，我必须计算出许多算法复杂度big-O，并将其与图上的理论值进行比较。我做了一个时间函数来计算算法的执行时间，但我没有找到一种方法来计算复杂度，并使用时间T和输入N绘制曲线。
有什么想法吗？
浏览 4提问于2016-04-22得票数 0
4回答
for (int i = 1; i < a; i++){
for(int j = 1; j < b; j = j + a){
Function() <-- O(1)
}
} 在这种情况下，外部循环将被执行‘a’次(O(A))，内循环将被执行'b/a‘次(O(b/a))。 那么总的时间复杂度将是O(a * b/a )= O(b)？ 我不是这个解释对不对..
浏览 31提问于2017-01-18得票数 2
回答已采纳
4回答
从上说
然而，不是像快速排序那样向两边递归，而是只在一边递归--一边是它正在搜索的元素。这将平均复杂度从O(n log n)降低到O(n)，最坏的情况是O(n^2)。
我不明白如何将平均复杂度降低到O(n)？不是更多的O(N/2 log N)仍然是O(N log N)。最坏的情况O(n^2)是怎样的？
浏览 6提问于2019-07-08得票数 17
回答已采纳
1回答
这是循环结构：
for (int i = 1 ; i < n ; i++) {
for (int j = 0 ; j < n ; j += i) {
// do stuff
}
}
我的猜测是O(nlogn)，因为它显然不能是O(n^2)，因为j中的增量在增加，而显然不能是O(n sqrt(n))，因为增量并不高。但我不知道如何正式证明这一点。
浏览 0提问于2018-03-12得票数 0
回答已采纳
3回答
合并排序复杂度
、、、
我们知道，对于以下算法，合并排序具有时间复杂度O(nlogn)：
void mergesort(n elements) {
mergesort(left half); ------------ (1)
mergesort(right half); ------------(2)
merge(left half, right half);
以下实现的时间复杂性是什么？
(1)
void mergesort(n elements) {
mergesort(first quarter); ------------ (1)
mergesort(remaining three qua
浏览 0提问于2013-10-14得票数 0
回答已采纳
3回答
for(int i=N; i>0; i=i/2)
irrelevant statement;
我被要求找到complexity类，我不确定我应该使用Big-Omega表示法还是Big-O表示法？但我假设它是O(N/2)，然后是O(N)，如果我去掉常量。
for (int i=0; i<N; i++)
for (int j = i+1; j<N; j++)
irrelevant statement;
对于这个，我相信它是O(N) * O(N+1) -> O(N^2 + N)，然后是O(N^2)，在我去掉N？
浏览 2提问于2010-10-17得票数 1
2回答
这是一个采访问题：
8x8棋盘上两个位置的最小表示形式是什么？
我找到了答案
但我无法理解作者试图表达的意思：
可以用n位表示2^n个值。但是，您可以表示2^n + 2^(n-1) + 2^(n-2) +.1= 2^(n+1) -1值。所以你可以用10位来表示2^11 -1= 2047个不同的值。
我并不是要求解释作者在他的回答中的建议，但我更感兴趣的是解决问题本身。据我所知，由于有64C2 = 2016方法来表示8x8板上的两块，所以所需的最小位数应该是11位，但有人建议，一位可以用10位来表示该板。多么?
浏览 3提问于2013-09-02得票数 2
回答已采纳
1回答
void Ordena(TipoItem *A, int n)
{
TipoItem x;
int i, j;
for (i = 1; i < n; i++)
{
for (j = n; j > i; j--)
{
if (A[j].chave < A[j - 1].chave)
{
x = A[j];
A[j] = A[j - 1];
A[j - 1]
浏览 3提问于2022-01-08得票数 0
回答已采纳
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
腾讯云开发者
