如何找到这种方法的渐近运行时间？

我被要求写这个方法，然后根据数组大小给出渐近运行时间。有人能向我解释这是如何完成的吗？如何找到这种方法的渐近运行时间？

public int doSomething(int[] nums) { 
    int count = 0; 

    for (int i = 0; i < nums.length; i++) 
     for (int j = 0; j < i; j++) 
      if (nums[i] > nums[j]) 
       count++; 

    return count; 
}

来源

2014-03-03 Jarmaloon

你知道些什么，到目前为止约渐近运行？这是一个很容易成为整章或更多章节的主题;这个问题对于SO的格式来说太宽泛了，因为你基本上是在寻求那个章节。请试试看，并提出更具体的问题。 – yshavit

你知道'if'后面有东西丢失了，对吗？ – keshlam

我知道他们有类似线性的。它们代表了该方法需要做多少功能才能看出它的运行方式。至于知道如何找到这个，我不知道。 – Jarmaloon

问题大小N是数量的长度。

从只有for语句的代码中决定渐近运行时的方法非常简单。

渐近运行时间由传统的符号一样

O(N)

这是一个简单的语句描述。我们只需要处理输入元素一次。

像你这样的嵌套for语句意味着我们需要多次检查每个num的值。

你在外循环中重复N次。你在内循环中重复N次。

还你怎么像打印

* 
** 
*** 
**** 
***** 
******

在三角形元素的数量成正比一个三角形N²

来源

2014-03-03 01:33:47

Downvoter请评论我的疑虑。 –

这帮了很大忙，谢谢！ – Jarmaloon

好运行时间通常是你有多少个步骤做。

渐近运行时间几乎是一样的，但你可以做一些“魔术”来简化你的结果。

在你的情况下，你有循环for (int i = 0; i < nums.length; i++)其中nums.length步骤。并且在每一步中，你都会做for (int j = 0; j < i; j++)。

嗯，首先，你能做的只有1，那么你做2步，比3个步骤等

运行时间是1 + 2 + 3 + 4 + 5 + 6 + .... + n，采用一系列的总和你：n*(n+1)/2

渐近运行时间是基于一些规则。在我们的例子中，你可以摆脱掉常量，只有n是很重要的，因此n*(n+1)/2 = Theta(n*(n)) = Theta(n^2)

结果：n^2

来源

2014-03-03 01:44:27 libik

这非常有帮助，谢谢！ – Jarmaloon

当人们写出像'n *（n + 1）/ 2 = Theta（n^2）'这样的记号时，我讨厌它，这是对符号的一种非常混淆的滥用。 'n *（n + 1）/ 2'是'Theta（n^2）'的一个实例，但绝不是_equal_。然而正如所写的，它与Integer.valueOf（n *（n + 1）/ 2）== Integer.valueOf（n * n）.class'一样荒谬。 – AJMansfield

@AJMansfield - 实际上你错了，两种语法都是正确的。 – libik

如何找到这种方法的渐近运行时间？

回答

相关问题