本文主要是介绍04 _ 复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这里会继续讲四个复杂度分析方面的知识点，最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均情况时间复杂度（average case time complexity）、均摊时间复杂度（amortized time complexity）。如果这几个概念你都能掌握，那对你来说，复杂度分析这部分内容就没什么大问题了。
最好、最坏情况时间复杂度
上一节我举的分析复杂度的例子都很简单，今天我们来看一个稍微复杂的。你可以用我上节教你的分析技巧，自己先试着分析一下这段代码的时间复杂度。
// n表示数组array的长度
int find(int[] array, int n, int x) {int i = 0;int pos = -1;for (; i < n; ++i) {if (array[i] == x) pos = i;}return pos;
}
你应该可以看出来，这段代码要实现的功能是，在一个无序的数组（array）中，查找变量x出现的位置。如果没有找到，就返回-1。按照上节课讲的分析方法，这段代码的复杂度是O(n)，其中，n代表数组的长度。
我们在数组中查找一个数据，并不需要每次都把整个数组都遍历一遍，因为有可能中途找到就可以提前结束循环了。但是，这段代码写得不够高效。我们可以这样优化一下这段查找代码。
// n表示数组array的长度
int find(int[] array, int n, int x) {int i = 0;int pos = -1;for (; i < n; ++i) {if (array[i] == x) {pos = i;break;}}return pos;
}
这个时候，问题就来了。我们优化完之后，这段代码的时间复杂度还是O(n)吗？很显然，咱们上一节讲的分析方法，解决不了这个问题。
因为，要查找的变量x可能出现在数组的任意位置。如果数组中第一个元素正好是要查找的变量x，那
这篇关于04 _ 复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
