注: 本博客仅提供一种解题思路与通用方法,具体问题请具体分析
👻 类型:while循环
🚀 思路
找出不满足while条件时,循环轮数 k 与输入规模 n 之间的关系
🚀 方法
1、确定代码中的循环变量、限制项、终止项:
👾 循环变量 i — 代码中进行循环的变量,例如下面的变量 i ;
👾 循环轮数 k — while循环不满足条件结束时,代码总共循环的次数;
👾 限制项 — 代码while限制条件的限制项,一般是关于循环变量 i 的函数,如下面代码的 i*i*i ;
👾 终止项 — 代码while限制条件的终止项,一般是关于输入规模 n 的函数,如下面代码的 n/2 ;
2、画表格找关系
3、得出关系式: ,反解k得到关于终止项n的关系式g(n)。
4、对k的关系式g(n)化简得到时间复杂度T(n)。
🚀 例题
👾 例题1
// 计算该算法的时间复杂度
void func(int n){
int i=1;
while(i<=n)
i=i*2;
}
(1)找出循环变量、限制项、终止项
(2)画表格,填表找关系
🤖 第1轮:循环变量初始化为1。while判断后,限制项 i = 1,循环变量变为 i = i*2 = 2;
🤖 第2轮:该轮初始循环变量为上轮的2。while判断后,限制项 i = 2,循环变量变为 i = i*2 = 4;
🤖 第3轮:该轮初始循环变量为上轮的4。while判断后,限制项 i = 4,循环变量变为 i = i*2 = 8;
🤖 第k轮:根据循环轮数k与限制项的关系可得此时限制项 i = 2^(k-1)。
(3)得出关系式: 反解k得
(4)化简k的关系式g(n)可得算法时间复杂度T(n) = O(logn)
👾 例题2
// 计算该算法的时间复杂度
void func(int n){
int i=0;
while(i*i*i <= n)
i++;
}
(1)找出循环遍历、限制项、终止项
(2)画表格,填表找关系
🤖 第1轮:循环变量初始化为0。while判断后,限制项 i*i*i = 0,循环变量变为 i = i+1 = 1;
🤖 第2轮:该轮初始循环变量为上轮的1。while判断后,限制项 i*i*i = 1*1*1 = 1,循环变量变为 i = i+1 = 2;
🤖 第3轮:该轮初始循环变量为上轮的2。while判断后,限制项 i*i*i = 2*2*2 = 8,循环变量变为 i = i+1 = 3;
🤖 第k轮:根据循环轮数k与限制项的关系可得此时限制项 i*i*i = (k-1)^3。
(3)得出关系式: 反解k得
(4)化简k的关系式g(n)可得算法时间复杂度T(n) = O(n^(1/3))
👾 例题3
// 计算该算法的时间复杂度
void func(int n){
int x=2;
while(x < n/2)
x = 2*x;
}
(1)找出循环遍历、限制项、终止项
(2)画表格,填表找关系
🤖 第1轮:循环变量初始化为2。while判断后,限制项 x= 2,循环变量 x = 2*x = 4;
🤖 第2轮:该轮初始循环变量为上轮的4。while判断后,限制项 x= 4,循环变量变为 x = 2*x = 8;
🤖 第3轮:该轮初始循环变量为上轮的8。while判断后,限制项 x= 8,循环变量 x = 2*x = 16;
🤖 第k轮:根据循环轮数k与限制项的关系可得此时限制项 x =2^k。
(3)得出关系式: ,反解k得
(4)化简k的关系式g(n)可得算法时间复杂度T(n) = O(logn)
👾 例题4
// 计算该算法的时间复杂度
void func(int n){
int x=0;
while(n >= (x+1)*(x+1))
x=x+1;
}
(1)找出循环遍历、限制项、终止项
(2)画表格,填表找关系(过程略,直接给出第k轮)
🤖 第k轮:根据循环轮数k与限制项的关系可得此时限制项 (x+1)^2 =k^2。
(3)得出关系式: 反解k得
(4)化简k的关系式g(n)可得算法时间复杂度T(n) = O(n^(1/2))
👾 例题5
// 计算该算法的时间复杂度
void func(int n){
int i=0,sum=0;
while(sum < n)
sum+ = ++i;
}
(1)找出循环遍历、限制项、终止项
(2)画表格,填表找关系(过程略,直接给出第k轮)
🤖 第k轮:根据循环轮数k与限制项的关系可得此时限制项 sum = [k(k+1)]/2。
(3)得出关系式: 反解k得
(4)化简k的关系式g(n)可得算法时间复杂度T(n) = O(n^(1/2))
👻 类型:for循环
🚀 思路
在外层循环限制下,找出总执行数T、轮数x、输入规模n的关系,联立求解。
🚀 方法
1、确定代码中的循环层数(以两层for循环为例)、内外层终止条件、内外层步长、关键操作语句:
👾 内外层变量 — 若是嵌套for循环,确定各层循环变量,如下面代码的 i、j ;
👾 外层终止条件 — 外层for循环终止的条件,如下面代码的 i<=n 条件;
👾 内层终止条件 — 内层for循环终止的条件,如下面代码的 j<=2*i 条件;
👾 外层步长 — 外层for循环的步长,如下面代码的 i++;
👾 内层步长 — 内层for循环的步长,如下面代码的 j++;
👾 关键操作语句 — 关键操作代码,一般在最内层for循环,如下面代码的 m++ 语句;
2、画表格找关系
3、确定轮数x与输入规模n的关系式①,轮数x与关键语句总执行次数T的关系式②;
4、联立①、②式,得到 总执行次数T 关于 输入规模n 的关系。化简得到时间复杂度T(n)。
附:等差、等比数列求和公式
🚀 例题
👾 例题1
// 计算该算法的时间复杂度
int m=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=2*i;j++)
m++;
(1)确定内外层终止条件,内外层步长
(2)画表格,填表找关系
🤖 第1轮:外层变量 i 初始化为1。内层变量 j 从1到 2 (2*i) ,关键语句执行 2 次;
🤖 第2轮:外层变量 i 为2。内层变量 j 从1到 4 (2*i) ,关键语句执行 4 次;
🤖 第3轮:外层变量 i 为3。内层变量 j 从1到 6 (2*i) ,关键语句执行 6 次;
🤖 最后一轮:最后一轮假设为x轮,则外层变量 i 为x。内层变量 j 从1到 2x (2*i) ,关键语句执行 2x 次;
(3)得出轮数x与输入规模n的关系式①(当i=n时外层循环结束,此时轮数x即为n轮):
(4)轮数x与关键语句总执行次数T的关系式②(将各轮执行次数累加):
(4)联立①、②式,得:
(5)化简得时间复杂度T(n) = O(n^2)
更直观的做法:
👾 例题2
// 计算该算法的时间复杂度
int count=0;
for(int k=1;k<=n;k*=2)
for(int j=1;j<=n;j++)
count++;
(1)确定内外层终止条件,内外层步长
(2)画表格,填表找关系(过程略,直接给出最后一轮)
🤖 最后一轮:最后一轮假设为x轮,则外层变量 k 为2^(x-1)。内层变量 j 与外层变量无关,从始至终都是从 1 到 n ,关键语句执行 n 次;最终终止条件为 k = n。
(3)得出轮数x与输入规模n的关系式①(当外层变量 k = 2^(x-1) = n 时外层循环结束):
(4)轮数x与关键语句总执行次数T的关系式②(将各轮执行次数累加):
(4)联立①、②式,得:
(5)化简得时间复杂度T(n) = O(nlogn)
👾 例题3
// 计算该算法的时间复杂度
int sum = 0;
for(int i=1;i<n;i*=2)
for(int i=0;j<i;j++)
sum++;
(1)确定内外层终止条件,内外层步长
(2)画表格,填表找关系(过程略,直接给出最后一轮)
🤖 最后一轮:最后一轮假设为x轮,则外层变量 i 为2^(x-1)。内层变量 j 从 0 到 i ,关键语句执行 i 次;最终终止条件为 i < n。
(3)得出轮数x与输入规模n的关系式①(当外层变量 n-1 < i < n 时循环结束,此时 i = 2^(x-1)):
(4)轮数x与关键语句总执行次数T的关系式②(将各轮执行次数累加):
(4)联立①、②式,得:
(5)化简得时间复杂度T(n) = O(n)
👾 例题4
// 计算该算法最后一行语句的频度在最坏情况下的时间复杂度(冒泡排序)
for(int i=n-1;i>1;i--)
for(int j=1;j<i;j++)
if(A[j]<A[j+1])
swap(A[j],A[j+1]); // 交换A[j]与A[j+1]的值
(1)确定内外层终止条件,内外层步长
(2)画表格,填表找关系(过程略,直接给出最后一轮)
🤖 最后一轮:最后一轮假设为x轮,则外层变量 i 为n-x。内层变量 j 从 0 到 i ,关键语句执行 i - 1 次;最终终止条件为 i < 1 ,即 i = 2。
(3)得出轮数x与输入规模n的关系式①(当外层变量 i > 1 即 i = n-x = 2 时循环结束):
(4)轮数x与关键语句总执行次数T的关系式②(将各轮执行次数累加):
(4)联立①、②式,得:
(5)化简得时间复杂度T(n) = O(n^2)
更直观的做法:
👻 类型:递归循环
🚀 思路
采用递归公式进行推导
🚀 方法
🤖 未完待续....
🌇 日落是免费的,春夏秋冬也是,不要觉得人生那么无望,希望你快乐。我们总是为许多遥不可及的事情奔波,却错过了路边的花开,傍晚落在身上的夕阳。忙着生活的同时记得去感受日常生活中的小细节,生活除了琐碎与平淡,还有可口的美食和无数盛开的花朵。晚风吹人醒,万事藏于心。我没说不公平也没说苦,我说我知道了