怎么自己做网站吓别人,网页搭配,国土系统网站建设用地受理表,动画设计基础什么是算法复杂度#xff1f; 简单来说算法复杂度是用来衡量一个算法的优劣的#xff0c;一个程序在运行时#xff0c;对运行时间和运行空间有要求#xff0c;即时间复杂度和空间复杂度。 目录
什么是算法复杂度#xff1f;
大O的渐近表达式
时间复杂度示例
空间复杂度…什么是算法复杂度 简单来说算法复杂度是用来衡量一个算法的优劣的一个程序在运行时对运行时间和运行空间有要求即时间复杂度和空间复杂度。 目录
什么是算法复杂度
大O的渐近表达式
时间复杂度示例
空间复杂度示例 常见复杂度对比 大O的渐近表达式 时间复杂度我们常常使用大O的渐近表示法
推导大O阶的规则 ●时间复杂度函数式T(N)中只保留高阶项去掉那些低阶项。 因为当N不断变大时低阶项对结果的影响越来越小当N无穷大时就可以忽略不计了 ●如果最高阶项存在且不是1则去除这个项目的常数系数。 因为当N不断变大这个系数对结果的影响不断变小当N无穷大时其就可以忽略不计了 ●T(N)如果没有N相关的项目只有常数项那么就用常数1替代所有加法。 时间复杂度示例
1.
// 计算Func2的时间复杂度
void Func2(int N)
{ int count 0; //1次for (int k 0; k 2 * N ; k) { count; //2*N次} int M 10; while (M--) { count; //10次} printf(%d\n, count);
} 得T(N)12*N10
由第一条和第二条规则得到时间复杂度O(N). 2.
// 计算Func3的时间复杂度
void Func3(int N, int M)
{ int count 0; for (int k 0; k M; k) //M次{ count; } for (int k 0; k N ; k) //N次{ count; } printf(%d\n, count);
} 得T(N)MN
由第一条规则或第二条规则得到时间复杂度O(N). 因为使用N代表其中增长速度快的哪一项则忽略掉增长速度慢的那一项当M和N增长速度一样时为2N则忽略系数 3.
// 计算Func4的时间复杂度
void Func4(int N)
{ int count 0; for (int k 0; k 100; k) //100次{ count; } printf(%d\n, count);
} 得T(N)100
由第三条规则得到时间复杂度O(1). 4.
// 计算strchr的时间复杂度
const char * strchr ( const char * str, int character)
{const char* p_begin s;while (*p_begin ! character){if (*p_begin \0)return NULL;p_begin;}return p_begin;
}
①最好情况 str的第一个字符就等于character得T(N)1则时间复杂度为O(1).
②平均情况 要查找的字符在str的中间得T(N)N/2则时间复杂度为O(N).
③最差情况 要查找字符在str的末尾得T(N)N则时间复杂度为O(N).
一般的我们取最差情况来表示算法的时间复杂度 ★某些算法存在分情况的时间复杂度 ●最坏情况任意输入规模的最大运行次数上界. ●平均情况任意输入规模的平均次数. ●最好情况任意输入规模的最小次数下界. 5.
// 计算BubbleSort的时间复杂度
void BubbleSort(int* a, int n)
{ assert(a); for (size_t end n; end 0; --end) { int exchange 0; for (size_t i 1; i end; i) { if (a[i-1] a[i]) { Swap(a[i-1], a[i]); exchange 1; } } if (exchange 0) break; }
}
通过上面的分析我们可尝试求出三种情况
最坏情况倒序O(N^2)
平均情况平均情况O(N^2
最好情况有序O(N) 6.
void func5(int n)
{int cnt 1;while (cnt n){cnt * 2;}
}
分析得T(N)log2n,即O(logn). 7.
// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{ if(0 N)return 1; return Fac(N-1)*N;
}
时间复杂度O(N). 空间复杂度示例 空间复杂度的表示也使用大O表达式。
1.
// 计算BubbleSort的时间复杂度
void BubbleSort(int* a, int n)
{ assert(a); //1次for (size_t end n; end 0; --end) //一次{ int exchange 0; //一次for (size_t i 1; i end; i) //一次{ if (a[i-1] a[i]) { Swap(a[i-1], a[i]); exchange 1; } } if (exchange 0) break; }
}
空间复杂度O(1). // 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{ if(N 0) return 1; return Fac(N-1)*N;
}开辟了N个函数栈帧空间复杂度为O(N) 常见复杂度对比
