【Java 面试题系列 06】时间复杂度是个啥？
【第 6 天】题目
时间复杂度是个啥？
参考答案
1、时间复杂度是什么？
通俗来讲，时间复杂度是用来衡量算法的一个指标（就好比我们会用学历去衡量一个人一样）。
对于算法的好坏，是有多个指标的，时间复杂度只不过是其中之一（衡量一个人优秀与否，除了学历也还有其他的参考点，不是么？）。
2、如何表示时间复杂度？大O表示法
若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))，O为算法的渐进时间复杂度，简称为时间复杂度。因为渐进时间复杂度用大写O来表示，所以也被称为大O表示法。
一脸懵逼是不是！！其实没必要去纠结它的概念性问题，你只需知道大O表示法的形式就是 O(n)。
3、如何计算时间复杂度？
按照下面的规则去计算时间复杂度
- 1. 如果运行时间是常数量级，则用常数1表示
- 2. 只保留时间函数中的最高阶项
- 3. 如果最高阶项存在，则省去最高阶项前面的系数
4、来两个例子看看
约定，在方法体内，每执行一次操作，我们记作 1 个时间单位。
先看个简单的示例：
public static int test1 (int n) {
n = + 2;
return n++;
}分析：代码 n = + 2; 执行一次，花费1个时间单位；代码 return n++; 执行一次，花费1个时间单位，一共就是 1 + 1 = 2，根据规则1，该方法的时间复杂度就是 O(1)。
再来一个示例：
public static int test2 (int n) {
int sum = 0;
// 循环 n + 1 次
for (int i = 0; i < n; i++) {
// 第 i 趟的时候，循环 n - i + 1 次
for (int j = 0; j < n - i; j++) {
// 代码块花费的时间单位 n + (n-1) + (n-2) + (n-3) + … + 1 = n*(n-1)/2
sum = + n;
}
}
return sum;
}参考注释，所以test1( ) 的时间时间复杂度为 n*(n-1)/2，参考规则，结果为 O(n^2)。
留个题目，练练手
//冒泡排序 升序
public static int[] bubbleSort (int[] arr) {
if (arr.length == 0) {
return arr;
}
//需要循环走访的次数
for (int i = 0; i < arr.length; i++) {
boolean isOrder = true;
//进行相邻元素的比较循环：从第一组到最后一组
for (int j = 0; j < arr.length - i - 1; j++) {
//如果前一个元素比后一个元素大，就交换位置，将较大的数后移
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isOrder = false;
}
}
if (isOrder) {
return arr;
}
}
return arr;
}那么，冒泡排序的最优时间复杂度和最坏时间复杂度分别是多少呢？
留言区
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-10-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读