网站商业授权含义,手工制作大全女生的最爱,白云网站建设多少钱,上海闵行区租房文章目录 算法效率时间复杂度时间复杂度的概念大O的渐进表示法计算实例 时间复杂度实例 常见复杂度对比例题 算法效率
算法效率是指算法在计算机上运行时所消耗的时间和资源。这是衡量算法执行速度和资源利用情况的重要指标。
例子#xff1a;
long long Fib(int N)
{if(N … 文章目录 算法效率时间复杂度时间复杂度的概念大O的渐进表示法计算实例 时间复杂度实例 常见复杂度对比例题 算法效率
算法效率是指算法在计算机上运行时所消耗的时间和资源。这是衡量算法执行速度和资源利用情况的重要指标。
例子
long long Fib(int N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}这是一个斐波那契函数用的是递归的计算方法每次创建函数就会在栈区开辟一块空间递归次数越多开辟空间越多 所以代码的简洁说明不了算法的效率 算法效率的评估主要包括时间复杂度和空间复杂度 时间复杂度时间复杂度描述了算法执行所需的时间随输入规模增加而增长的趋势。常见的时间复杂度包括常数时间O(1)、线性时间O(n)、对数时间O(log n)、平方时间O(n²)等。通过分析算法中关键操作的执行次数来确定时间复杂度通常使用大O符号表示。 空间复杂度空间复杂度描述了算法在执行过程中所需的额外存储空间随输入规模增加而增长的趋势。常见的空间复杂度包括常数空间O(1)、线性空间O(n)、对数空间O(log n)等。通过分析算法中使用的数据结构和辅助空间来确定空间复杂度。
评估算法效率时我们希望选择具有更低时间复杂度和空间复杂度的算法以提高程序的执行速度和资源利用率。但需要注意的是时间复杂度和空间复杂度通常存在着一定的取舍关系有时需要在时间和空间之间做出权衡。
除了时间复杂度和空间复杂度还可以考虑一些实际情况下的算法效率问题如最坏情况、平均情况和最好情况下的执行时间以及算法在特定硬件环境下的性能等。综合考虑这些因素可以更全面地评估算法的效率。
为了提高算法效率我们可以采用一些常见的优化方法如减少循环次数、使用合适的数据结构和算法、剪枝和缓存等。同时也可以借助工具和框架来提升算法效率如并行计算、GPU加速、分布式计算等。
时间复杂度
时间复杂度的概念
在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。
例子计算Func1中的count语句执行了多少次
void Func1(int N)
{int count 0;for (int i 0; i N ; i){for (int j 0; j N ; j){count;}}for (int k 0; k 2 * N ; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}两个循环嵌套就是N^2,再一个单独的循环2*N加上10 那么 FNN^22*N10; N10时F(N)130 N100时F(N)10210 N1000时F(N)1002010 会发现N越大F(N)越接近N^2 在实际计算时间复杂度中我们其实不一定要精准的计算出执行的次数只需要大概的执行次数那么这里我们使用大O的渐进表示法
大O的渐进表示法
大O符号Big O notation是用于描述函数渐进行为的数学符号。是一种用于衡量算法时间复杂度的渐进表示方法
推导大O阶方法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。
用大O的渐进表示法Func1的时间复杂度为O(N^2)
N10时F(N)100 N100时F(N)10000 N1000时F(N)1000000 通过计算我们发现这样的表示方法去掉那些对结果影响不大的项简明了洁表示出执行次数 对于一些算法会有好坏的情况对于这种情况我们取最坏的情况 例如在一个长度为N数组中搜索一个数据x 最好情况1次找到 最坏情况N次找到 平均情况N/2次找到 时间复杂度O(N);
计算实例 void Func2(int N)
{int count 0;for (int k 0; k 2 * N ; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}在这里M是一个常数项N是一个未知数所以我们可以先把常数项略去然后就只剩下2N通过计算规则,省去最高项的常数那么这个函数的时间复杂度为O(N); void Func3(int N, int M)
{int count 0;for (int k 0; k M; k){count;}for (int k 0; k N ; k){count;}printf(%d\n, count);
}在这里M与N都是未知数且它们是同阶的所以对于这种情况就要分类讨论 M与N差不多大那么时间复杂度O(M)或O(N) M远大于N时间复杂度O(M) N远大于M时间复杂度O(N) void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}这里给出了明确的次数所以时间复杂度为O(1); const char * strchr ( const char * str, int character );查找字符串中第一个出现的字符返回指向 C 字符串 str 中第一个出现的字符的指针。 终止空字符被视为 C 字符串的一部分。因此也可以定位它以检索指向字符串末尾的指针。 这个就是在字符串中寻找一个字符对于这种就要分好坏情况 最好1次最坏N次时间复杂度一般看最坏时间复杂度为 O(N)。 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;}
}这是一个冒泡排序很明显这个两个循环在嵌套外循环执行1次内循环就得执行N次那么外循环执行N次总共就执行N^2次 时间复杂度O(N^2); int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n-1;// [begin, end]begin和end是左闭右闭区间因此有号while (begin end){int mid begin ((end-begin)1);if (a[mid] x)begin mid1;else if (a[mid] x)end mid-1;elsereturn mid;}return -1;
}这是一个二分查找函数也叫折半查找我们以最坏的情况去看每循环一次这个数组的长度就会减半假设以N表示数组的长度我们要在数组中寻找一个数那么假设寻找了x次那么通过计算2^xN;再通过换算就是xlog2 N;2是对数的底数由于底数不好表示所以对于这个函数的时间复杂度就是为O(logN); long long Fac(size_t N)
{
if(0 N)
return 1;
return Fac(N-1)*N;
}这是一个阶乘递归函数每递归一次N减1直至为0才返回 那么时间复杂度为O(N) long long Fib(size_t N)
{
if(N 3)
return 1;
return Fib(N-1) Fib(N-2);
}这是开头的例子斐波那契递归函数每次在函数中就会递归到两个函数中去 递归到最后会发现像个金字塔一样全部加起来F(N)1248……2(N-1),由数学的等比求和公式得F(N)2^N-1; 那么时间复杂度为F(N)2^N; 时间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
实例 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(1) long long* Fibonacci(size_t n)
{if(n0)return NULL;long long * fibArray (long long *)malloc((n1) * sizeof(long long));fibArray[0] 0;fibArray[1] 1;for (int i 2; i n ; i){fibArray[i] fibArray[i - 1] fibArray [i - 2];}return fibArray;
}这里用了malloc函数在堆区开辟了N个额外空间所以 空间复杂度为O(N) long long Fac(size_t N)
{if(N 0)return 1;return Fac(N-1)*N;
}这里用了递归的方法每递归一次就会在栈帧中开辟一次空间总共开辟N次每次空间内为常数次大所以 空间复杂度O(N); 常见复杂度对比 例题 这里用三种办法来解答 第一种 时间复杂度O(N^2) 空间复杂度O(1) 这里利用这种方法就是用两个循环嵌套最终就得出了复杂度
第二种 通过开辟额外空间将对应位置的数字进行放入新数组中最后再返回到原数组中 时间复杂度:O(N) 空间复杂度:O(N) void rotate(int* nums, int numsSize, int k){//开辟额外空间int* new(int*)malloc(sizeof(int)*numsSize);//当k长度超过数组长度时k%numsSize;memcpy(new,numsnumsSize-k,sizeof(int)*k);memcpy(new,nums,sizeof(int)*(numsSize-k));memcpy(nums,new,sizeof(int)*numsSize);free(new);}第三种 利用倒置再倒置的方法就将数组右旋 时间复杂度:O(N) 空间复杂度:O(1) //将数组进行倒置
void reserve(int* sem,int left,int right)
{while(leftright){int tmpsem[left];sem[left]sem[right];sem[right]tmp;left;right--;}}
void rotate(int* nums, int numsSize, int k){k%numsSize;//如果k的长度大于numsize需要取余//利用部分数组倒置在全数组倒置的方法进行轮转reserve(nums,0,numsSize-k-1);reserve(nums,numsSize-k,numsSize-1);reserve(nums,0,numsSize-1);}
