算法的复杂性 [英] Complexety of algorithm

问题描述

嗨

我正在尝试计算一个算法的复杂性，总和是多少

1 * log（1）+ 2 * log（2）+ ... +（n-1）* log（n-1）+ n * log（n）

给O（）？

我猜测它是O（log（n）* n ^ 2）但它是吗​​？


亲切的问候，

Allan Ebdrup

解决方案

假设log（）函数本身是O（1），那么复杂性

应为O（n）。


此外，我已经做了很长时间了，但是我怀疑有一个公式可以取代循环，并减少它是

O（1）。


-

-

真相，< br $>
James Curran

[以前的VC ++ MVP]


主页： www.noveltheory.com 工作： www .njtheater.com

博客： www.honestillusion.com 日工作： www.partsearch.com

" Allan Ebdrup" <共**** @ ofir.com>在消息中写道

新闻：#j ************** @ tk2msftngp13.phx.gbl ...

嗨我正在尝试计算算法的复杂性总和是什么？1 * log（1）+ 2 * log（2）+ ... +（n-1）* log（n-1 ）+ n * log（n）
给O（）？
我猜它是O（log（n）* n ^ 2）但它是吗​​？

亲切的问候，
Allan Ebdrup

" James Curran" < JA ********* @ mvps.org>在消息中写道

新闻：％2 **************** @ TK2MSFTNGP09.phx.gbl ...

假设log（）函数本身就是O（1），那么复杂性应该是O（n）。

日志部分至少有O（ log（n））复杂性和1 + 2 + 3 + ... + n是O（n ^ 2）

>日志部分至少有O（log（n））复杂性


是什么给了你这个想法？请考虑以下因素：

f（n）= n * 1000000000.f（n）的复杂性是多少。 O（10亿

n）？上）？实际上，它只是O（1），因为只需要一步即可完成
计算值。

的价值总是只有一步。

和1 + 2 + 3 + ...... + n是O（n ^ 2）
再次废话。它的*结果*在n ^ 2的范围内，但计算它的过程

涉及n个步骤，因此是O（n）：

int sum = 0;

for（int i = 1; i< = n; ++ i）

{

sum + = i;

}

事实上，当我提到O（1）的算法时，我想到的是这个特定的总和。总结1 ... n如上所述是O（n），但是

因为高斯被证明是一个孩子，同样的答案可以通过以下方式实现：


f（n）=（（n + 1）*（n / 2）

是O（1）（步数与n的值无关）< br $> b $ b -

-

真相，

James Curran

[以前的VC ++ MVP]


主页： www.noveltheory.com 工作： www.njtheater.com

博客： www.honestillusion.com 日工作： www.partsearch.com

Allan Ebdrup"< co **** @ ofir.com>在消息中写道

新闻：#a ************** @ TK2MSFTNGP10.phx.gbl ..." James Curran"< ja **** *****@mvps.org>写在消息中
新闻：％2 **************** @ TK2MSFTNGP09.phx.gbl ...

假设log（）函数本身是O（1） ，那么复杂性应该是O（n）。
日志部分至少有O（log（n））复杂性，1 + 2 + 3 + ... + n是

O（n ^ 2）

Hi
I''m trying to calculate a complexety of an algorithm what does the sum
1*log(1) + 2*log(2) + ... + (n-1)*log(n-1) + n*log(n)
give in O()?
I''m guession it''s O(log(n)*n^2) but is it?

Kind Regards,
Allan Ebdrup

解决方案

Assuming that the log() function is itself O(1), then the complexity
should be O(n).

Further, It''s been a long time since I''ve done such things, but I
suspect that there a formula which replaces the loop, and reduces it to
O(1).

--
--
Truth,
James Curran
[erstwhile VC++ MVP]

Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com

"Allan Ebdrup" <co****@ofir.com> wrote in message
news:#j**************@tk2msftngp13.phx.gbl...

Hi
I''m trying to calculate a complexety of an algorithm what does the sum
1*log(1) + 2*log(2) + ... + (n-1)*log(n-1) + n*log(n)
give in O()?
I''m guession it''s O(log(n)*n^2) but is it?

Kind Regards,
Allan Ebdrup

"James Curran" <ja*********@mvps.org> wrote in message
news:%2****************@TK2MSFTNGP09.phx.gbl...

Assuming that the log() function is itself O(1), then the complexity
should be O(n).

the log part has at least O(log(n)) complexety and the 1+2+3+...+n is O(n^2)

> the log part has at least O(log(n)) complexety

Whatever gave you that idea? Consider the following:
f(n) = n * 1000000000. What is the complexity of f(n). O(1 billion
n) ? O(n)? Actually, it''s just O(1), because there is exactly one step to
be done calculate the value. There will always be just one step regardly of
the value of n.

and the 1+2+3+...+n is O(n^2) Again nonsense. It''s *result* is in the range of n^2, but the process
to calculate it involves n steps, and therefore is O(n):
int sum = 0;
for(int i = 1; i <= n; ++i)
{
sum += i;
}
In fact, that particular summation is what I was thinking of when I
mentioned an algorithm of O(1). Summing 1...n as I did above is O(n), but
as Gauss proved as a child the same answer can be achieve via:

f(n) = ((n +1) * (n / 2)

which is of O(1) (the number of steps is unrelated to the value of n)
--
--
Truth,
James Curran
[erstwhile VC++ MVP]

Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com

"Allan Ebdrup" <co****@ofir.com> wrote in message
news:#a**************@TK2MSFTNGP10.phx.gbl... "James Curran" <ja*********@mvps.org> wrote in message
news:%2****************@TK2MSFTNGP09.phx.gbl...

Assuming that the log() function is itself O(1), then the complexity
should be O(n).
the log part has at least O(log(n)) complexety and the 1+2+3+...+n is

O(n^2)

这篇关于算法的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！