牢记：Tn是当前变量的执行次数
我们要做的就是讲Tn从各种嵌套中拎出来，用n表示。
每层循环的变量ijk表示都不一样，但是实际上都是指n在执行过程中的变化
)
一、常数阶
// 常数阶
int result = 100; //运行程序只执行一次
result ++ ; //执行一次
System.out.println ("Hello!"+result); //执行一次
上面算法的运行的次数的函数为f(n)=3，根据推导大O阶的规则1，每次运行程序每条语句执行一次，所以这个算法的时间复杂度仍旧是O(1)，我们可以称之为常数阶。
例：
void fun4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
++count;
}
printf("%d\n", count);
}
fun3的基本操作的执行了100次，通过推导大O阶方法知道，时间复杂度为O（1）。
二、线性阶
//线性阶
for(int i=0;i<n;i++){
System.out.println(result[i]); //执行一次
}
线性阶主要要分析循环结构的运行情况。
上面算法循环体中的代码执行了n次，因此时间复杂度为O(n)，实际上，在for循环里面的所有时间复杂度为O(1)的语句总的时间复杂度都是O(n)。
三、对数阶
// 对数阶
int result=1;
while(result<n){
result=result*2; //时间复杂度为O(1)
}
可以看出上面的代码， result=result*2; 随着result每次乘以2后，都会越来越接近n，当result大于等于n时就会退出循环（限制条件）。
如果循环的次数为T，所以2^T=n于是T=log₂n，因此得出这个算法的时间复杂度为O(logn)。
例题：
二分查找
//二分查找法
int BinarySearch(int* a, int n, int x) {
assert(a);
int begin = 0;
int end = n - 1;
while (begin < end) {
int mid = ((end - begin) >> 1) + begin; //计算end与begin的中间值，右移1位相当于除以2
if (a[mid] < x) {begin = mid - 1;}
else if(a[mid]>x){end = mid;}
else {return mid;}
}
return -1;
}
对于BinarySearch函数来说，它存在
最好情况:执行1次
最坏情况:约执行logN次，这里的logN是以2为底，以N为对数。
这里我们考虑最坏情况，时间复杂度为：O(logN)。分析如下：
第一次查找：在长度为N的数组中查找值，取中间值进行比较
第二次查找：在长度为N/2的数组中查找值，取中间值进行比较
第三次查找：在长度为N/(2^2)的数组中查找值，取中间值进行比较
…
第logN次查找：在长度为N/(2^logN)的数组中查找值，即在长度为1的数组中查找，无论是否找到均跳出循环，结束查找。
四、平方阶
4.1
// 平方阶
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
System.out.println(result[i][j]); //执行一次
}
}
这是一个循环嵌套的语句，很明显内层循环的时间复杂度在讲到线性阶时就已经得知是O(n)，又经过了外层循环n次，那么这段算法的时间复杂度则为O(n²)。
4.2
void fun(int n){
int i,j,x=0;
for(i=1;i<n;i++){
for(j=n;j>=i+1;j--){
x++;
}
}
}
4.3
void fun(int n){
int i=0;
while(i*i*i<=n){
i++;
}
}
4.4
4.5
4.6冒泡排序
void Swap(int* a, int* b) {
int c = *a;
*a = *b;
*b = c;
}
//冒泡排序 --从小到大
void BubbleSort(int* a, int n) {
assert(a);//异常处理
for (int end = n; end > 0; --end) {
int exchange = 0;
for (int i = 1; i < end; ++i) {
if (a[i - 1] > a[i]) {
//两个数据进行比较，前面一个数据大于后一个数据
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
//如果遍历整个数组，发现没有数据进行交换，即每个元素均小于等于后一个元素
//则无须在进行排序，直接结束循环即可
if (exchange == 0)
break;
}
}
对于BubbleSort函数来说，它存在
最好情况:数组为顺序，执行N次
最坏情况:数组为逆序，执行N*(N+1)/2次
五、多个复杂度组合：顺序结构
// 多个复杂度组合
for(int i=0;i<n;i++){
for(int j=0;j<n;i++){
System.out.println(result[i][j]); //执行一次
}
}
for(int i=0;i<n;i++){
System.out.println(result[i]); //执行一次
}
对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。所以对于以上的代码，时间复杂度为O(n²)。
六、多个复杂度组合：选择结构
// 多个复杂度组合
if(flag){
for(int i=0;i<n;i++){
for(int j=0;j<n;i++){
System.out.println(result[i][j]); //执行一次
}
}
}else{
for(int i=0;i<n;i++){
System.out.println(result[i]); //执行一次
}
}
对于条件判断语句，总的时间复杂度等于其中时间复杂度最大的路径的时间复杂度。所以对于以上的代码，时间复杂度为O(n²)。
七、多个复杂结构：嵌套结构
void fun(int n){
int i,k;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
k=1;
while(k<=n){
k = 5*k;
}
}
}
}
八、递归
//求阶乘
long long Factorial(int N) {
return N < 2 ? N : N * Factorial(N - 1) ;
}
例文章来源：https://www.toymoban.com/news/detail-404968.html
//斐波那契函数
long long Fibonacci(int N) {
return N < 2 ? N : Fibonacci(N - 1) + Fibonacci(N - 2);
}
Fibonacci函数的时间复杂度为O（2^N），分析过程如下：
文章来源地址https://www.toymoban.com/news/detail-404968.html
到了这里，关于时间复杂度计算-例题集合的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
