算法效率的分析
一、输入规模与执行次数
1.输入规模就是一个程序输入次数，或者是一个方法的形参。
2.执行次数就是程序中代码的执行次数
#include
//1.输入规模与执行次数的分析(n与T之间的关系)
void print1(int n){//n就是print1方法的输入规模
printf("hello\n");//1次
printf("hello\n");//1次
printf("hello\n");//1次
}//该方法的输入规模为n 执行次数为3，输入规模与执行次数的的关系为 Tn(n)=3
void print2(int n){//n就是print2方法的输入规模
for(int i = 0; i < n; i++){
printf("hello\n");//n次
printf("hello\n");//n次
}
printf("输出完成\n");//1次
}//该方法的输入规模为n 执行次数为2n，输入规模与执行次数的的关系为 Tn(n)=2n+1
void print3(int n){//n就是print3方法的输入规模
for(int i = 0; i < n; i *= 2){
printf("hello\n");//log2n次
printf("hello\n");//log2n次
}
printf("输出完成\n");//1次
}//该方法的输入规模为n 执行次数为2n，输入规模与执行次数的的关系为 Tn(n)=2*log2n+1
void print4(int n){//n就是print4方法的输入规模
printf("开始输出\n");//1次
for(int i = 0; i < n; i++){
printf("hello\n");//n次
printf("hello\n");//n次
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
printf("hello2\n");//n^2次
printf("hello2\n");//n^2次
}
}
printf("输出完成\n");//1次
}//该方法的输入规模为n 执行次数为2n，输入规模与执行次数的的关系为 Tn(n)=2*n^2 + 2*n + 2
int main(){
}
二、算法的时间复杂度：就是衡量算法的时间开销的方法。
#include
//2.时间复杂度O()的分析:由于直接输代码执行的次数太麻烦，我使用时间复杂度来分析算法，
//T()与O()之间的关系：只保留T()的最高次项，并将最高次项的系数改为1
void print1(int n){//n就是print1方法的输入规模
printf("hello\n");//1次
printf("hello\n");//1次
printf("hello\n");//1次
}//该方法的输入规模为n 执行次数为3，输入规模与执行次数的的关系为 Tn()=3
//该方法的时间复杂度为O(1)
void print2(int n){//n就是print2方法的输入规模
for(int i = 0; i < n; i++){
printf("hello\n");//n次
printf("hello\n");//n次
}
printf("输出完成\n");//1次
}//该方法的输入规模为n 执行次数为2n，输入规模与执行次数的的关系为 Tn()=2n+1
//该方法的时间复杂度为O(n)
void print3(int n){//n就是print3方法的输入规模
for(int i = 0; i < n; i *= 2){
printf("hello\n");//log2n次
printf("hello\n");//log2n次
}
printf("输出完成\n");//1次
}//该方法的输入规模为n 执行次数为2n，输入规模与执行次数的的关系为 Tn(n)=2*log2n+1
//该方法的时间复杂度为O(log2n)
void print4(int n){//n就是print4方法的输入规模
printf("开始输出\n");//1次
for(int i = 0; i < n; i++){
printf("hello\n");//n次
printf("hello\n");//n次
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
printf("hello2\n");//n^2次
printf("hello2\n");//n^2次
}
}
printf("输出完成\n");//1次
}//该方法的输入规模为n 执行次数为2n，输入规模与执行次数的的关系为 Tn(n)=2*n^2 + 2*n + 2
//该方法的时间复杂度为O(n^2)
int main(){
}
三、空间复杂度：空间复杂度就是一个方法或程序运行所需要的空间大小。
#include
//3.空间复杂度S()的分析：空间复杂度就是一个方法或程序运行所需要的空间大小
//(其实就是程序中变量所占的字节数大小),
//与时间复杂度一样只保留最高次项并将最高次项的系数改为1。
void test1(int n){//int类型的变量占用四个字节
int i;//int类型的变量占用四个字节
int num[n];//int类型的数组占用4*n个字节
}//该方法的空间复杂度为O(4n+8) =>(简化为) O(n)
void test2(int n){//int类型的变量占用四个字节
int i;//int类型的变量占用四个字节
int j;//int类型的变量占用四个字节
int num[n][n];//int类型的二维数组占用n^2个字节
}//该方法空间复杂度为O(n^2+12 ) =>(简化为) O(n^2)
int main(){
}