哦，与Summations合作？

 

我知道这不是严格的编程问题，但它是一个计算机科学问题，所以我希望有人能帮助我。

我一直在研究算法的作业，并计算出几种算法的Big-Oh，Big-Omega，Theta等。 我通过查找他们的C和N0值证明他们，并且一切进展顺利。

然而，我遇到了我在集合中的最后两个问题，我正在努力找出如何去做（而谷歌没有什么帮助）。

我以前不必弄清楚总结的大哦/欧米茄。

我最后两个问题是：

  • 证明i2的Σ（i = 1到n）是O（N3）

    • 和

  • 证明[log2i]的Σ（i = 1到n）是Ω（n log n）

    • 我的问题是，我如何显示？

    例如，在第一个中，直觉上我看不出i2的总和是O（N3）。 第二个让我更加困惑。 有人可以解释如何展示这些总结的Big-Oh和Big-Omega吗？

    我的猜测是问题陈述的含义是，如果你总结了一些计算结果，其中运行时间与第一种情况下的i2成比例，并且第二种情况与log2i成比例。 在这两种情况下，总和的运行时间由总和内的较大N值“支配”，因此，两者的总体大O评估将为N * O（f），其中f是函数，重新总结。

    http://en.wikipedia.org/wiki/Big_O_notation

    对于任何f（N），g（m）= O（f（m））的N个重复是O(N*f(m)) ）。

    如果g（n）= 0（f（n））且f是单调的，则i * g（i）的i = 1..N的总和为O(N*f(N)) 。

    定义g（n）= O（f（n））如果对于所有n> m存在一些c，m，则g(n)<=c*f(n)

    总和是对于i i*f(i) i = 1..N。

    如果f在i中是单调的，这意味着每个项都是<= if（N）<= Nf（N）。 因此，总和小于N*c*f(N)所以总和为O(N*f(N)) （由使得g（n）= O（f（n））的相同c，m所见证）

    当然，log_2（x）和x ^ 2都是单调的。

  • Σ（i = 1至n）i2 = n（n + 1）（2n + 1）/ 6，其为O（n3）。

  • 注意：（n！）2 =（1 n）（2（n-1））（3（n-2））...（（n-1）2）（n 1）
    =Π（i = 1至n）i（n + 1-i）
    > =Π（i = 1至n）n
    [例如，因为对于每个i = 1到n，（i-1）（ni）> = 0。与Graham / Knuth / Patashnik，第4.4节]
    = nn。
    因此，n！ > = nn / 2，因此
    Σ（i = 1到n）log i = logΠ（i = 1到n）i = log n！ > = log nn / 2 =（n / 2）log n，即Ω（n log n）。

    • 链接地址: http://www.djcxy.com/p/43103.html

    上一篇: Oh works with Summations?

    下一篇: Allow an infrared device to send a signal to control the monitor of a PC