网站换主机换域名,北京网站建设机构,成都网站建设制作服务,怎么弄数据库备份做网站相关代码gitee自取#xff1a;
C语言学习日记: 加油努力 (gitee.com)
接上期#xff1a;
学C的第三十四天【程序环境和预处理】_高高的胖子的博客-CSDN博客 1 . 算法效率 #xff08;1#xff09;. 什么是数据结构#xff1a; 数据结构(Data Structure)是计算机存储、…
相关代码gitee自取
C语言学习日记: 加油努力 (gitee.com) 接上期
学C的第三十四天【程序环境和预处理】_高高的胖子的博客-CSDN博客 1 . 算法效率 1. 什么是数据结构 数据结构(Data Structure)是计算机存储、组织数据的方式 指相互之间存在一种或多种特定关系的数据元素的集合。 2. 什么是算法 算法(Algorithm)就是定义良好的计算过程 它取一个或一组的值为输入并产生出一个或一组值作为输出。 简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。 3. 算法的复杂度 算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源。 因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的 即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢 而空间复杂度主要衡量一个算法运行所需要的额外空间。 在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。 但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。 所以我们如今已经不需要再特别关注一个算法的空间复杂度。 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2 . 时间复杂度 1. 时间复杂度的概念 在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。 一个算法执行所耗费的时间从理论上说是不能算出来的 只有你把你的程序放在机器上跑起来才能知道。 但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦 所以才有了时间复杂度这个分析方式。 一个算法所花费的时间与其中语句的执行次数成正比例 算法中的基本操作的执行次数为算法的时间复杂度。 即 找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。 图例Func1执行的基本操作次数 上图得到的Func1执行的基本次数为 F(N) N^2 2*N 10 但实际我们计算时间复杂度时我们其实并不一定要计算精确的执行次数 而只需要大概执行次数那么这里我们使用大O的渐进表示法。 2. 大O的渐进表示法 大O符号Big O notation是用于描述函数渐进行为的数学符号。 推导大O阶方法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。 使用大O的渐进表示法以后 F(N) N^2 2*N 10 第一步10 变为 1 第二步保留最高阶项 N^2 第三步最高项相乘常数为1不用去除 所以Func1的时间复杂度O(N^2) N 10 F(N) 100 N 100 F(N) 10000 N 1000 F(N) 1000000 通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项 简洁明了的表示出了执行次数。 大O的渐进表示法本质计算的是算法属于哪个量级。 另外有些算法的时间复杂度存在最好、平均和最坏情况 可查看下方案例四 最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界) 例如在一个长度为N数组中搜索一个数据x 最坏情况N次找到 平均情况N/2次找到 最好情况1次找到 在实际操作下一般情况关注的是算法的最坏运行情况 所以数组中搜索数据时间复杂度为O(N) 3. 常见时间复杂度计算案例 案例一 //示例一
//计算Func2的时间复杂度
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);
} 图示 案例二 //示例二
//计算Func3的时间复杂度
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);
}图示 案例三 //示例三
//计算Func4的时间复杂度
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count N);
} 图示“cpu技术太强了” 案例四 //示例四
//计算strchr的时间复杂度
const char* strchr(const char* str, int character);
//strchr库函数在str字符数组中查找一个字符 图示 案例五 //示例五
#include stdio.h
//计算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;}}
} 图示 案例六 //示例六
//计算BinarySearch的时间复杂度
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 mid 1;}else if (a[mid] x){end mid - 1;}else{return mid;}}return -1;
} 图示 案例七 //示例七
//计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if (0 N){return 1;}return Fac(N-1)*N;
}图示 案例八 //示例八
//计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if (N 3){return 1;}return Fib(N - 1) Fib(N - 2);
} 图示 4. 常见时间复杂度对比 一般算法常见的复杂度如下表 5201314O(1)常数阶3n 4O(n)线性阶3n^2 4n 5O(n^2)平方阶3log(2)n 4O(logn)对数阶2n 3nlog(2)n 14O(nlogn)nlogn阶n^3 2n^2 4n 6O(n^3)立方阶2^nO(2^n)指数阶 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 3 . 空间复杂度 1. 空间复杂度的概念 空间复杂度也是一个数学表达式 是对一个算法在运行过程中额外临时占用存储空间大小的量度。 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义 所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。 注意 函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等) 在编译期间已经确定好了 因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 2. 常见空间复杂度计算案例 案例一 //计算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;}}
}图示 案例二 //计算Fibonacci的空间复杂度
//返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if (n0){return NULL;}long long* fibArray (long long*)malloc((n 1) * 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;
}图示 案例三 //计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if (N 0){return 1;}return Fac(N-1)*N;
} 图示 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 4 . 复杂度的oj练习 1. 时间复杂度练习消失的数字 对应链接 面试题 17.04. 消失的数字 - 力扣LeetCode 题目 解决思路一使用等差数列公式 假设数组nums包含从0到n的所有整数 那么就可以使用 0N等差公式 计算出一个结果 该结果就等于 0~n的各数相加总和 再用这个结果 减去 数组中的值 结果就是消失的数字的值 图示 对应代码 int missingNumber(int* nums, int numsSize){int N numsSize;int ret N*(N1)/2;for(int i 0; i N; i){ret - nums[i];}return ret;
}解决思路二异或法 先用 0 异或 完整的0~N各值 再用该异或的结果来 异或 nums数组少一个值 因为异或后相同为0相异为1 此时两对值中相同的值就会异或为0 nums少的一个值异或后就会得到该值 图示 对应代码 int missingNumber(int* nums, int numsSize){int N numsSize;int x 0; //用来保存异或后的结果for(int i 0; i N; i){x ^ i;}for(int i 0; i N; i){x ^ nums[i];}return x;
}2. 空间复杂度练习轮转数组 对应链接 189. 轮转数组 - 力扣LeetCode 题目要求时间复杂度为O(N)空间复杂度为为O(1) 解决思路一整体右旋 将原数组分为两部分 假设需要右旋k个数字 以原数组末尾k个数字为一组剩下其他数字为一组 两组进行调换即可实现 图示 对应代码 void rotate(int* nums, int numsSize, int k){//用空间换时间int n numsSize; //数组长度int* tmp (int*)malloc(sizeof(int)*n);k % n; //确保要右旋个数小于数组大小//直接使用memcpy函数进行调换memcpy(tmp, numsn-k, sizeof(int)*k); //把后k个值移到前面// tmp : 起始位置// numsn-k : 数组nums后k个值的起始位置// sizeof(int)*k 拷贝k个int大小的数据memcpy(tmpk, nums, sizeof(int)*(n-k)); //把后k个值移到前面// tmpk : 拷贝到tmpk的位置因为上面把后k个值放在了前面// nums : 数组nums开始位置// sizeof(int)*(n-k) 拷贝(n-k)个int大小的数据//再赋给数组numsmemcpy(nums, tmp, sizeof(int)*n);//释放开辟的动态空间free(tmp);
} 解决思路二逆置 将原数组的前 n-k 个数逆置 后 k 个数也逆置 最后再整体逆置即可实现 图示 对应代码 //逆置函数
void reverse(int* a, int left, int right)
{while(left right){int tmp a[left];a[left] a[right];a[right] tmp;left;--right;}
}void rotate(int* nums, int numsSize, int k){k % numsSize;//逆置前 n-k 个数reverse(nums, 0, numsSize-k-1);//逆置后 k 个数reverse(nums, numsSize-k, numsSize-1);//最后整体逆置reverse(nums, 0, numsSize-1);
}
