数组算法及其时间复杂度分析
数组算法及其时间复杂度分析
提问于 2016-03-04 08:11:33
我应该分析这段代码，并说明它的时间复杂性，但我无法理解代码本身的功能，它是如何改变数组a的？
我也不明白下面两个操作: 1) foobar[ai]++；所以你用a数组的元素替换了foobar中的零？但是++能做什么呢？
2) aoutPos++=1；这首先递增outPos，并在整个for循环中保持不变？
public static void foo(int[] a, int b) {
int [] foobar = new int[b+1];
for (int i = 0; i<foobar.length; i++)
foobar[i]=0;
for (int i = 0; i<a.length; i++)
foobar[a[i]]++;
int outPos = 0;
for (int i=0; i<foobar.length; i++)
for (int j=0; j<foobar[i]; j++)
a[outPos++]=i;
}就时间复杂度而言，我认为它是O(n^2)。前两个for循环在固定时间内运行。但在我看来，第三个嵌套循环的最坏情况似乎是foobar中的最后一个元素很大，然后它将是二次的？
回答 2
Stack Overflow用户
发布于 2016-03-04 09:55:01
它是Counting Sort实现，
其中a[]存储要排序的数组，b是a[]中的最大整数
foobar[]是大小为b的计数数组
让N = sizeof(a), M = b来表示通用符号，
前两个循环：
如果O(N)，，
- ，
a[]中有3‘10，- 初始化计数数组使元素为零
棘手的第三个循环：
在外部循环中，毫无疑问，O(M)
- Inner循环，您必须考虑代码总(最大)
j可以增加的次数：Sum(foobar[]) = sizeof(a) = N，所以实际上这个循环，在整个外部循环迭代中，最多只能执行N次。所以两个循环作为一个整体是<
- >d32>，而不是直观地
所以总的复杂度是：O(N) + O(M) + O(N+M) = O(N+M)。
小贴士如果你发现第三个循环的复杂性很难理解，可以这样想：
这是一个0和游戏。如果有一些foobar[z] is large，那么就有很多foobar[j] = 0，这几乎意味着跳过这样的i的内部循环。否则，所有foobar[j]的大小约为平均大小。
很难对i的每次迭代进行分析，但很容易将内部循环作为一个整体进行分析，因为我们知道foobar[]的总和是一个常数。
Stack Overflow用户
发布于 2016-03-04 08:23:15
这看起来像是一个counting sort实现。考虑到N(项数)是数组a的长度，M(最大可能项数)是b，其时间复杂度为O(N+M)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/35785629
复制相关文章
相似问题
腾讯云开发者
