我的问题在标题里。经过几个小时的思考和在谷歌上查找网站，我得出的结论是，我不太确定如何解决这个问题，或者它是否正确。也许你们可以给予我一些建议，以更快或更容易的方式解决这些问题。任何帮助是赞赏！
该算法的成本函数为：
时间复杂度O（n）
外循环被执行大约log（n）次（因为“i”在每次迭代中被加倍），并且内循环在外循环的每次迭代中（在外循环的第一次迭代上）被执行至多n次，并且在外循环的每次后续迭代中至多执行一半次数。这样的话，时间复杂度为O（n）。
public float[] normalize (float[] seq) {
int n = seq.length;
float sum = 0;
int cnt = 0;
int i;
for (i = 1; i < n; i = i + i ) {
for ( int j = 0; j < i; j++) {
sum = sum + seq [j];
}
cnt += i;
}
float[] res = new float [n];
while (i >= 0) {
if (i < n) {
res [i] = seq[i] / (sum / cnt);
}
i--;
}
return res;
}该算法的成本函数为：
时间复杂度O（n）
外循环被执行大约log（n）次（因为“i”在每次迭代中被加倍），并且内循环在外循环的每次迭代中（在外循环的第一次迭代上）被执行至多n次，并且在外循环的每次后续迭代中至多执行一半次数。这样的话，时间复杂度为O（n）。
1条答案
按热度按时间92dk7w1h1#
是的，是
O(n log n)。1.对于
(int i = 0; i < n; i = i + i)，它确实是一个log（n）性能特性。不是“近似地”，而是 * 精确地 * -近似被融入性能特征的概念中。1.然后，对于每一个，你循环通过
0-i，其中i的最坏/平均情况都是来自n的恒定引用，或多或少-因此，O(n)。将两者结合起来，得到O(n log n)。1.剩下的是
O(n)，常数因子“不计数”，所以O(2n * log n)仍然只是简化的O(n log n)。这种分析通常是确定这些事情的唯一方法。理论上你可以把它画出来;毕竟，'这个函数是
O(n log n)意味着：如果你制作一个2D折线图，Y轴上是“花费的时间”，X轴上是“n的值”，你实际上填写了值（生成一些n=1的输入）。运行它几次并计算运行时间的平均值。让我们假设它是5 msec。在x=1，y=5上加一个点。现在在n=2时运行它。假设是7毫秒。在x=2，y=7上加一个点。继续现在画一条线，大致符合点。瞧！
O(n log n)表示：如果你向右看得足够远，用零表示你必须看多远，曲线看起来就像数学函数描述的曲线的最右边部分：y = x * log(x)，不管日志是哪个基（它们看起来都一样）。它只是看起来像什么，因此，常数因子是不相关的，因此，任何不“控制”的东西都可以省略（例如。y=x^2 + x和y = x^2看起来完全一样，如果你看得足够远的话;这就是为什么O(x^2 + x)只是官样文章，唯一要说的是“这是曲线最终的样子”，而+ x的东西对外观没有影响，因此，包含它没有意义，因此，O(n)符号永远不会。无论如何，这为您提供了另一种方法：实际上把它画出来，并把它和一些标准曲线进行比较。但我怀疑这比推理要少。