网站建设要点,wordpress 吧,建外贸营销型网站,国外的素材网站文章目录 1.数据结构前言1.1 数据结构1.2 算法1.3 如何学好数据结构和算法 2.算法效率2.1 复杂度的概念2.2 复杂度的重要性 3.时间复杂度3.1 大O的渐进表示法3.2 时间复杂度计算示例3.2.1 示例13.2.2 示例23.2.3 示例33.2.4 示例43.2.5 示例53.2.6 示例63.2.7 示例7 4.空间复杂… 文章目录 1.数据结构前言1.1 数据结构1.2 算法1.3 如何学好数据结构和算法 2.算法效率2.1 复杂度的概念2.2 复杂度的重要性 3.时间复杂度3.1 大O的渐进表示法3.2 时间复杂度计算示例3.2.1 示例13.2.2 示例23.2.3 示例33.2.4 示例43.2.5 示例53.2.6 示例63.2.7 示例7 4.空间复杂度4.1 空间复杂度计算示例4.1.1 示例14.1.2 示例2 5.常见复杂度对比6.复杂度算法题6.1 旋转数组 1.数据结构前言
1.1 数据结构
数据结构(Data Structure)是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用所以我们要学各式各样的数据结构。
如线性表、树、图、哈希等 1.2 算法
算法(Algorithm):就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。 1.3 如何学好数据结构和算法
秘诀1
死磕代码
秘诀2
画图画图画图思考 2.算法效率
例题
力扣189.轮转数组
给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。
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;}
}这个算法是没有问题的但是在力扣运行会报错显示超过时间限制。
这就涉及到了复杂度这个概念。 2.1 复杂度的概念
算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏一般 是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。
在计算 机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计 算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 2.2 复杂度的重要性
复杂度在校招中的考察已经很常见要重点掌握。 3.时间复杂度
定义在计算机科学中算法的时间复杂度是一个函数式T(N)它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率那么为什么不去计算程序的运行时间呢 因为程序运行时间和编译环境和运行机器的配置都有关系比如同一个算法程序用一个老编译器进行编译和新编译器编译在同样机器下运行时间不同。 同一个算法程序用一个老低配置机器和新高配置机器运行时间也不同。 并且时间只能程序写好后测试不能写程序前通过理论思想计算评估。 那么算法的时间复杂度是一个函数式T(N)到底是什么呢这个T(N)函数式计算了程序的执行次数。
通过c语言编译链接章节学习我们知道算法程序被编译后生成二进制指令程序运行就是cpu执行这 些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式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) { for (int j 0; j N ; j) { count; } } for (int k 0; k 2 * N ; k) { count; } int M 10; while (M--) { count; }
}分析
Func1 执行的基本操作次数
T (N) N^2^ 2 ∗ N 10 N 10 T(N) 130 N 100 T(N) 10210 N 1000 T(N) 1002010 通过对N取值分析对结果影响最大的一项是N^2^
实际中我们计算时间复杂度时计算的也不是程序的精确的执行次数精确执行次数计算起来还是很麻烦的(不同的一句程序代码编译出的指令条数都是不一样的)计算出精确的执行次数意义也不大因为我么计算时间复杂度只是想比较算法程序的增长量级也就是当N不断变大时T(N)的差别。
上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小所以我们只需要计算程序能代表增长量级的大概执行次数复杂度的表示通常使用大O的渐进表示法。 3.1 大O的渐进表示法
大O符号Big O notation是用于描述函数渐进行为的数学符号 推导大O阶规则 时间复杂度函数式T(N)中只保留最高阶项去掉那些低阶项因为当N不断变大时低阶项对结果影响越来越小当N无穷大时就可以忽略不计了。 如果最高阶项存在且不是1则去除这个项目的常数系数因为当N不断变大这个系数对结果影响越来越小当N无穷大时就可以忽略不计了。 T(N)中如果没有N相关的项目只有常数项用常数1取代所有加法常数。 通过以上方法可以得到 Func1 的时间复杂度为O(N2 ) 3.2 时间复杂度计算示例
3.2.1 示例1
// 计算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);
} Func2执行的基本操作次数
F (N) 2N 10
Func2的时间复杂度为O(N) 3.2.2 示例2
// 计算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);
}Func3执行的基本操作次数
F (N) M N
因此Func3的时间复杂度为O(MN) 3.2.3 示例3
// 计算Func4的时间复杂度
void Func4(int N)
{ int count 0; for (int k 0; k 100; k) { count; } printf(%d\n, count);
}Func4执行的基本操作次数
F (N) 100
根据推导规则第1条得出
Func4的时间复杂度为O(1) 3.2.4 示例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;
}strchr执行的基本操作次数 若要查找的字符在字符串第一个位置则 F (N) 1 若要查找的字符在字符串最后的一个位置则 F (N) N 若要查找的字符在字符串中间位置则 F (N) N/2 因此strchr的时间复杂度分为 最好情况O(1) 最坏情况O(N) 平均情况O(N) 总结 通过上面我们会发现有些算法的时间复杂度存在最好、平均和最坏情况。 最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界) 大O的渐进表示法在实际中一般情况关注的是算法的上界也就是最坏运行情况。 3.2.5 示例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; }
}BubbleSort执行的基本操作次数 若数组有序则 F (N) N 若数组有序且为降序则 F (N) [N ∗ (N 1)] / 2 若要查找的字符在字符串中间位置则 因此BubbleSort的时间复杂度取最差情况为O(N2) 3.2.6 示例6
void func5(int n)
{int cnt 1;while (cnt n){cnt * 2;}
}当n2时执行次数为1 当n4时执行次数为2 当n16时执行次数为4 假设执行次数为x 则2x n 因此执行次数x log n 因此func6的时间复杂度取最差情况为O(log2n) 注意 log~2~n 、log n 、 lg n 的表示。 当n接近无穷大时底数的大小对结果影响不大。因此一般情况下不管底数是多少都可以省略不写即可以表示为log n 不同书籍的表示方式不同以上写法差别不大建议使用log n 3.2.7 示例7
// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{ if(0 N) return 1; return Fac(N-1)*N;
}调用一次Fac函数的时间复杂度为O(1)
而在Fac函数中存在n次递归调用Fac函数
因此
阶乘递归的时间复杂度为O(n) 4.空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。
空间复杂度不是程序占用了多少bytes的空间因为常规情况每个对象大小差异不会很大所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。
注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 4.1 空间复杂度计算示例
4.1.1 示例1
// 计算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; }
}函数栈帧在编译期间已经确定好了只需要关注函数在运行时额外申请的空间。
BubbleSort额外申请的空间有exchange等有限个局部变量使用了常数个额外空间
因此空间复杂度为O(1) 4.1.2 示例2
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{ if(N 0) return 1; return Fac(N-1)*N;
}Fac递归调用了N次额外开辟了N个函数栈帧每个栈帧使用了常数个空间
因此空间复杂度为O(N) 5.常见复杂度对比 6.复杂度算法题
6.1 旋转数组
思路1:
时间复杂度 O(n2)
循环K次将数组所有元素向后移动K位代码不通过
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;}
}粗略估计O(K*N) O(n2) 思路2:
空间复杂度 O(n)
申请新数组空间先将后k个数据放到新数组中再将剩下的数据挪到新数组中
void rotate(int* nums, int numsSize, int k)
{int newArr[numsSize];for (int i 0; i numsSize; i) {newArr[(i k) % numsSize] nums[i];}for (int i 0; i numsSize; i) {nums[i] newArr[i];}
}时间复杂度O(nn) O(2n) O(n)
空间复杂度O(n)因为创建了一个新数组 思路3:
时间复杂度O(N)
空间复杂度 O(1) 前n-k个逆置4 3 2 1 5 6 7 后k个逆置 4 3 2 1 7 6 5 整体逆置 5 6 7 1 2 3 4
void reverse(int* nums,int begin,int end)
{while(begin end){//交换nums里面begin到end区域的数字int tmp nums[begin];//交换left和right的数据nums[begin] nums[end];nums[end] tmp;begin;end--;}
}void rotate(int* nums, int numsSize, int k)
{k k%numsSize;reverse(nums,0,numsSize-k-1);//前n-k个逆置reverse(nums,numsSize-k,numsSize-1);//后k个数据逆置reverse(nums,0,numsSize-1);//整体逆置
}
