什么是时间复杂性？如何找到它？

cl25kdpy 于 2021-07-06 发布在 Java

关注(0)|答案(2)|浏览(348)

这个问题在这里已经有答案了：

大o，你是怎么计算/近似的(23个答案）
如何找到算法的时间复杂度（9个答案）
7年前关门了。
我已经阅读了这么多的参考资料，但仍然坚持理解什么是时间复杂性。我读到的资料是基于各种公式的，我明白这一点 O(n) 用来表示时间复杂度，但我不知道怎么表达。请任何人用一种可以理解的清楚的方式向我解释这个原则。

Java time-complexity

来源：https://stackoverflow.com/questions/65580152/begginer-time-complexy-exercise

2条答案

按热度按时间

jfewjypa1#

参考：如何计算时间复杂度算法
我发现了一篇关于如何计算任何算法或程序的时间复杂度的好文章
计算时间复杂度最常用的度量是big o表示法。这去除了所有常数因子，因此当n接近无穷大时，可以根据n来估计运行时间。一般来说，你可以这样想：

statement;

是恒定的。语句的运行时间不会随n而改变。

for ( i = 0; i < N; i++ )
     statement;

是线性的。环路的运行时间与n成正比。当n加倍时，运行时间也加倍。

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ )
    statement;
}

是二次的。两个回路的运行时间与n的平方成正比。当n加倍时，运行时间增加n*n。

while ( low <= high ) {
  mid = ( low + high ) / 2;
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid + 1;
  else break;
}

是对数的。算法的运行时间与n除以2的次数成正比。这是因为算法在每次迭代中将工作区域分成两半。

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

是nlog（n）。运行时间由n个对数循环（迭代或递归）组成，因此该算法是线性和对数的组合。
一般来说，一维的每一项做一件事是线性的，二维的每一项做一件事是二次的，将工作面积一分为二是对数的。还有其他大o度量，如立方、指数和平方根，但它们并不常见。大o表示法被描述为o（），其中是度量。快速排序算法可以描述为o（nlog（n））。
请注意，这些都没有考虑最佳、平均和最坏情况度量。每个都有自己的大o符号。还要注意，这是一个非常简单的解释。大o是最常见的，但它也比我展示的更复杂。还有其他符号，如大Ω、小o和大θ。在算法分析课程之外，你可能不会遇到这些问题
编辑：
现在的问题是 log n 进入方程：
对于每一步，在上半部分和下半部分递归调用算法。
因此-所需的总步骤数，是指如果将问题每一步分为2，则从n到1所需的次数。
公式为：n/2^k=1。因为2^logn=n，我们得到k=logn。因此算法需要的迭代次数是o（logn），这将使算法 O(nlogn) 此外，大o表示法为我们提供了易于计算的独立于平台的近似算法，它可以将算法的“族”划分为复杂度的子集，并让我们很容易地比较它们。
您也可以检查这个问题，以获得更多的阅读：时间复杂性的程序使用递归方程