专门做喷涂设备的网站,郑州一站式网站搭建,衡水做网站改版,深圳网站建设公司建设目录 算法效率时间复杂度大O渐进表示法时间复杂度计算案例 空间复杂度空间复杂度案例 复杂度算法题 算法效率
算法在编写成可执行程序后#xff0c;运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好坏#xff0c;⼀般是从时间和空间两个维度来衡量的#xf… 目录 算法效率时间复杂度大O渐进表示法时间复杂度计算案例 空间复杂度空间复杂度案例 复杂度算法题 算法效率
算法在编写成可执行程序后运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好坏⼀般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。 时间复杂度主要衡量⼀个算法的运行快慢⽽空间复杂度主要衡量⼀个算法运行所需要的额外空间。 在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度有时我们会用空间复杂度来分担时间复杂度。
时间复杂度
定义在计算机科学中算法的时间复杂度是⼀个函数式T(N)它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率那么为什么不去计算程序的运行时间呢
因为程序运行时间和编译环境和运行机器的配置都有关系比如同⼀个算法程序用⼀个老编译器进⾏编译和新编译器编译在同样机器下运行时间不同。同⼀个算法程序用⼀个老的低配置机器和新的高配置机器运行时间也不同。并且时间只能程序写好后测试不能写程序前通过理论思想计算评估。
算法的时间复杂度是⼀个函数式T(N)到底是什么呢这个T(N)函数式计算了程序的执行次数。假设每个语句编译的时间都一样那程序语句执行的次数就与时间成正比用次数就可以间接反映算法的时间。 假设同一个问题算法a程序T(N)N,算法b程序T(N)N^2那算法a就优于算法b。 举个例子
// 请计算⼀下Func1中count语句总共执⾏了多少
次
void Func1(int N)
{
int count 0;
for (int i 0; i N ; i)//外循环n次
{
for (int j 0; j N ; j)//内循环n次
{
count;//一共循环n*n次
}
}
for (int k 0; k 2 * N ; k)//循环2n次
{
count;
}
int M 10;
while (M--)//循环10次
{
count;
}
}每个循环的语句都标注在程序后面得出T(N)如下 有的会问那些int M等语句不算吗但是那些算上的话一共就两次与N^2和2N比太小了这里就直接忽略了。 T(N)N^22N10; 实际中我们计算时间复杂度时计算的也不是程序的精确的执行次数精确执行次数计算起来还是很麻烦的(不同的⼀句程序代码编译出的指令条数都是不⼀样的)计算出精确的执行次数意义也不大因为我们计算时间复杂度只是想比较算法程序的增长量级也就是当N不断变大时T(N)的差别上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小所以我们只需要计算程序能代表增长量级的大概执行次数复杂度的表示通常使用大O的渐进表示法。
大O渐进表示法
大O符号Big O notation是用于描述函数渐进行为的数学符号。
时间复杂度函数式T(N)中只保留最高阶项去掉那些低阶项因为当N不断变大时低阶项对结果影响越来越小当N无穷大时就可以忽略不计了。 用上面的列子来说T(N)就可以写为N^2后面的低阶项和常数就可以忽略了。如果最高阶项存在且不是1则去除这个项目的常数系数因为当N不断变大这个系数对结果影响越来越小当N无穷大时就可以忽略不计了。 例如2N^2 与 N^2是等价的当N无穷大系数2的影响可以忽略。T(N)中如果没有N相关的项⽬只有常数项⽤常数1取代所有加法常数。
时间复杂度计算案例
案例1
void Func2(int N)
{
int count 0;
for (int k 0; k 2 * N ; k)//循环n次
{
count;
}
int M 10;
while (M--)//循环10次
{
count;
}
printf(%d\n, count);
}T(N)2N10; 最高阶是2N后面的低阶项和常数项忽略最高阶的的系数也可以忽略 所以这段程序的时间复杂度就是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; 当MN时复杂度为O(N); 当MN时复杂度为O(M); 当MN时复杂度为O(MN); 因为他有两个影响次数的参数分别是M和N复杂度算的是情况最坏的情况也就是M和N都趋于无穷那他们两个共同决定运行次数 所以复杂度就是O(MN);
案例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渐进表示法第三条可得 时间复杂度为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;
}第一种情况 要找的字符串在源字符串前面Y(N)常数时间复杂度O(I) 第二种情况 在中间位置T(N)N/2;时间复杂度O(N) 第三种情况 在末尾T(N)N;时间复杂度O(N) 取最坏结果时间复杂度为O(N)
案例5
// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{
if(0 N)
return 1;
return Fac(N-1)*N;
}递归就相当与循环调用一个函数N次 通过判断可知这个递归函数一共调用N次 所以它的时间复杂度O(N)。
空间复杂度
空间复杂度也是⼀个数学表达式是对⼀个算法在运行过程中因为算法的需要额外临时开辟的空间。 空间复杂度不是程序占用了多少bytes的空间因为常规情况每个对象大小差异不会很大所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运⾏时候申请的额外空间来确定。
空间复杂度案例
案例1
// 计算BubbleSort的时间复杂度
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end n//1次; end 0; --end)
{
int exchange 0;//2次
for (size_t i 1//3次; i end; i)
{
if (a[i-1] a[i])
{
Swap(a[i-1], a[i]);
exchange 1;
}
}
if (exchange 0)
break;
}
}由分析可知在运行时创建的临时变量有三个T(N)3 所以空间复杂度为O(1);
案例2
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{
if(N 0)
return 1;
return Fac(N-1)*N;
}在c语言学习中函数的使用要创建栈帧空间前面分析了这个递归要运行N次这个函数运行一次就创建一个函数栈帧空间所以T(N)N 它的空间复杂度O(N)。
复杂度算法题
轮转N个数据 数组元素 0 1 2 3 4 轮转1次4 0 1 2 3 轮转2次3 4 0 1 2
void rotate(int* nums, int numsSize, int k) {
while(k--)
{
int end nums[numsSize-1];
for(int i numsSize - 1;i 0 ;i--)
{
nums[i] nums[i-1];
}
nums[0] end;
}
}外循环K次内循环N次。 可知一共循环KN次。 最欢结果让数据轮转N次即T(N)NNN^2; 时间复杂度O(N^2)。
现在出个问题让它的时间复杂度降低。 思路1刚开始提到可以用空间复杂度来分担时间复杂度。 代码实现
void rotate(int* nums, int numsize, int k) {
int newnums[numsize];//创建大小为N的字符串
for(int i 0;inumsize;i)
{
newnums[i]nums[(ik)%numsize];
}
for(int i0;inumsize;i)
{
nums[i]newnums[i];
}时间复杂度T(N)2N– O(N); 空间复杂度T(N)N–O(N)。
思路2 如图数组里存放5个数轮转2次。 先操作前半部分交换第一个与第二个数据如果前半部分数据较多交换第二个跟倒数第二的数据依次类推 交换后数组变成2 1 3 4 5 然后相同的方法交换后半部分 交换后数组2 1 5 4 3 然后交换整个数组 交换后3 4 5 1 2 交换完成。 空间复杂度O(1),时间复杂度O(N)
void swap(int* nums,int left, int right)
{while (left right){int tmp nums[left];nums[left] nums[right];nums[right] tmp;left;right--;}}
void rotate(int* nums, int numsize, int k) {k% numsize;swap(nums, 0,k-1);swap(nums, k,numsize-1);swap(nums, 0,numsize-1);
}这个思路不难就是不容易想出来。它既节省了空间复杂度还优化了时间复杂度。 ----------------------------------------------分隔符 时间复杂度与空间复杂度就介绍完了希望对各位看官有所帮助。 有错请在评论区指正谢谢。
