O时间复杂度

 

我一直在做一些关于Big-O的自学。 我明白如何给算法提供以下符号的例子：

上）： 

for(int i = 0; i < n; i++)
    sum++;

O（N ^ 2）： 

for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

O（N ^ 3）： 

for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

我遇到了这些我不太了解的符号。 我如何根据算法给出这些例子？

也许我应该这样说：写一个算法，其运行时间的比例为：

  • O（（N ^ 3）/ 4）
  • 记录n ^ 3
  • O（（日志^ 2）N）+ O（n）的
  • 4 ^ N
  • N R个3/2

    • 我担心你误会了“大O”符号。

    符号不是“表达”的算法。 相反，Big-O符号描述算法的属性。

    所以不是“O（N）可以表示为XXX”，而是“算法XXX具有O（N）的复杂性”。

    也就是说，询问具有一定复杂度的算法的例子是非常合理的; 你已经列出了一些。 解决您的问题：

    O（4 ^ n）与O（e ^ n）相同，通常写为O（exp（n））（试着理解它为什么相同）。 O（4 ^ n）属于具有“指数复杂度”（EXPTIME）的算法类。 数学/ CS中的许多重要问题具有指数复杂性（或几乎呈指数级的复杂度）。

    具有指数复杂度的算法将是例如对离散对数问题的天真解决方案。

    对于其他的复杂性，我不能举一个例子，但你可能会发现一个用google搜索一下。

    你给出的算法严格来说不是Big-O而是Theta。 Big-O是一个渐近上限，意味着在某些更糟糕的情况下，输入的运行时间将是给定的，但并非针对所有输入，其中Theta是一个严格意义上的运行时间永远是这样的。 考虑一个排序算法，例如一个已经排序的列表作为输入，或者一个搜索算法，其中要找到的东西是列表中的第一个元素（二进制搜索在这种情况下如何与线性搜索进行比较）。

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

    上一篇: O time complexity

    下一篇: Oh : How can O(n) + O(n) + ... + O(n) be equal to O(n^2)?