php网站目录系统,制作免费个人网站,天津网站建设交易,龙岗网站建设哪家便宜本章重点
算法效率时间复杂度空间复杂度常见时间复杂度以及复杂度OJ练习
1.算法效率
1.1 如何衡量一个算法的好坏 如何衡量一个算法的好坏呢#xff1f;比如对于以下斐波那契数列#xff1a; long long Fib(int N)
{
if(N 3)
return 1;return Fib(N-1) Fib(N-2);
}斐…本章重点
算法效率时间复杂度空间复杂度常见时间复杂度以及复杂度OJ练习
1.算法效率
1.1 如何衡量一个算法的好坏 如何衡量一个算法的好坏呢比如对于以下斐波那契数列 long long Fib(int N)
{
if(N 3)
return 1;return Fib(N-1) Fib(N-2);
}斐波那契数列的递归实现方式非常简洁但简洁一定好吗那该如何衡量其好与坏呢 这种递归的斐波那契数列在计算大数字的时候不见得很好用。 这是因为其时间复杂度和空间复杂的原因 1.2 算法的复杂度
算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。 ##blue## 时间复杂度:主要衡量一个算法的运行快慢 空间复杂度:主要衡量一个算法运行所需要的额外空间。 在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。
所以我们如今已经不需要再特别关注一个算法的空间复杂度。
2.时间复杂度
2.1 时间复杂度的概念 时间复杂度的定义在计算机科学中算法的时间复杂度是一个函数(数学中的函数)它定量描述了该算法的运行时间。 一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。 即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。 例如 // 请计算一下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);
}F(N)N^22*N10 N 10 F(N) 130 N 100 F(N) 10210 N 1000 F(N) 1002010 实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。 像上面的count次数来说根据数据的慢慢变大N^2更能代表该段程序的时间复杂度 2.2 大O的渐进表示法
大O符号Big O notation是用于描述函数渐进行为的数学符号。
推导大O阶方法
用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中只保留最高阶项。如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后上述Func1的时间复杂度为O(N^2)
N 10 F(N) 100N 100 F(N) 10000N 1000 F(N) 1000000
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项 简洁明了的表示出了执行次数。
有些算法的时间复杂度存在最好、平均和最坏情况
最坏情况: 任意输入规模的最大运行次数(上界)平均情况: 任意输入规模的期望运行次数最好情况: 任意输入规模的最小运行次数(下界)
例如在一个长度为N数组中搜索一个数据x
最好情况1次找到最坏情况N次找到平均情况N / 2次找到
在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N)
2.3常见时间复杂度计算举例
实例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);
}基本操作执行了2N10次 通过推导大O阶方法知道时间复杂度为 O(N) 实例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);
}基本操作执行了MN次有两个未知数M和N 时间复杂度为 O(N)O(MN) 两个未知数位阶一样所以都得留下 实例3 //3.计算Func4的时间复杂度
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}基本操作执行了100次通过推导大O阶方法时间复杂度为 O(1) 用常数1取代运行时间中的所有加法常数。 O(1)代表的是常数次 这样写其实是因为我们现在电脑的CPU运行的足够快 这里我们可以写个代买来运行测试一下 includetime.h
int main()
{size_t begin clock();//引头文件time.h//这个函数是用来记录时间的到运行它的时候会记录一个时间单位毫秒size_t n 0;for (size_t i 0;i 1000000000;i){n;}size_t end clock();printf(%d毫秒\n, end - begin);return 0;
}实例4 //4. 计算strchr的时间复杂度
const char* strchr(const char* str, int character);这里简单介绍一下strchr函数 就是在字符串str里面找一个字符character找不到str找到就返回str地址 大家也可以去cplusplus.com里面看 strchr函数的详细解释 如果整个字符串有n个元素要找其中的一个元素这个时候就有一下几种情况 最好O(1)最坏O(N)平均O(N/2) 这个时候我们一般取最坏的情况O(N) 实例5冒泡排序的时间复杂度 // 5.计算BubbleSort的时间复杂度
void BubbleSort(int* a, int n)
{for (size_t end n; end 1; --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;}
}按最坏情况来看 第一趟冒泡排序是N-1第二趟N-2第三趟N-3…最后一次是1 可以看出来是需要进行N*(N-1)/2 次循环 基本操作执行最好N次最坏执行了 N * (N-1)/2 次 通过推导大O阶方法时间复杂度一般看最坏时间复杂度为 O(N^2 实例6二分查找的时间复杂度 //6. 计算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;elsereturn mid;}return -1;
}二分法查找每次查找查找区间缩小一半查找多少次出2多少次 这里可以吧二分法查找想象成折纸更容易理解一些 基本操作执行最好1次最坏O(logN)次 log以2为底的N不好在计算机上表示所以会简写为logN其他底数不能省略 时间复杂度为 O(logN) 实例7 //7. 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}现基本操作递归了N次时间复杂度为 O(N) 实例8 //8. 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}基本操作递归了2N次时间复杂度为O(2N)。 像一个细胞分裂一样n次分裂就是2^N个 3.空间复杂度 空间复杂度也是一个数学表达式是对一个算法在运行过程中临时额外占用存储空间大小的量度(如:函数中传入不算) 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。 空间复杂度计算规则类似于时间复杂度不是精确值而实估计值 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定 实例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;}
}使用了常数个额外空间所以空间复杂度为 O(1) 实例2 // 计算Fibonacci的空间复杂度
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if (n 0)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;
}动态开辟了N个空间和若干个常数项所以空间复杂度为 O(N) 实例3 // 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if (N 0)return 1;return Fac(N - 1) * N;
}递归调用了N次开辟了N个栈帧每次开辟后没有被销毁 每个栈帧使用了常数个空间。 空间复杂度为O(N 这里如果使用循环就是O(1) 这里注意时因为空间是可以重复利用的所以不会对一个数据重复开辟 4.复杂度的oj练习
4.1消失的数字
消失的数字 - 力扣LeetCode
数组nums包含从0到n的所有整数但其中缺了一个。
请编写代码找出那个缺失的整数(在 O(n) 时间内完成)注意本题相对书上原题稍作改动示例 1输入[3,0,1]
输出2示例 2输入[9,6,4,2,3,5,7,0,1]
输出8方法一公式计算
将数组的大小1进行累加 减去 将数组中的所有数加起来即可求得
int main()
{int arr[] { 9,6,4,2,3,5,7,0,1 };int sz sizeof(arr) / sizeof(arr[0]);int add1 0;int add2 0;int i 0;for (i 0;i sz;i){add1 arr[i];}for (i 0;i sz 1;i){add2 i;}printf(%d\n, add2 - add1);return 0;
}这里的时间复杂度为O(N) 空间复杂度为O(1) 方法二异或
将n个数组元素于0~n1的字符串异或即可求得
int main()
{int arr[] { 9,6,4,2,3,5,7,0,1 };int sz sizeof(arr) / sizeof(arr[0]);int i 0;int add 0;for (i 0;i sz;i){add ^ arr[0];}for (i 0;i sz1;i){add ^ i;}printf(%d\n, add);return 0;
}这里的时间复杂度为O(N) 空间复杂度为O(1) 方法三:排序二分查找 时间复杂度 O(N*logN) 4.2 旋转数组
轮转数组 - 力扣LeetCode 给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4] 示例 2: 输入: nums [-1,-100,3,99], k 2 输出:[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100] 提示 1 nums.length 105 -231 nums[i] 231 - 1 0 k 105 进阶 尽可能想出更多的解决方案至少有 三种 不同的方法可以解决这个问题。 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗 方法一一个一个的挪
void func1(int *a,int sz,int k)
{for (int i 0;i k;i){int tmp a[sz-1];for (int j sz;j 0;j--){a[j - 1] a[j - 2];}a[0] tmp;}
}
int main()
{int k 0;scanf(%d, k);int arr[9] { 1,2,3,4,5,6,7,8,9 };int sz sizeof(arr) / sizeof(arr[0]);k % sz;//方法一//func1(arr,sz,k);for (int i 0; i sz;i){printf(%d , arr[i]);}printf(\n);return 0;
}但是这个方法在LeetCode上面编译不过去因为时间复杂度有点大O(NK)
方法二另一个数组进行存储
牺牲空间去换取时间效率用另一个数组来进行存储再复制回去
void func2(int* a, int sz, int k)
{int a2[10] { 0 };int n sz - k;int i 0;int j 0;for (i;i n;i){a2[i] a[i];}for (j0;j k;j,i){a2[i] a[i];}for (j 0;j sz;j){a[j] a2[j];}
}
int main()
{int k 0;scanf(%d, k);int arr[9] { 1,2,3,4,5,6,7,8,9 };int sz sizeof(arr) / sizeof(arr[0]);k % sz;//方法二func2(arr, sz, k);for (int i 0; i sz;i){printf(%d , arr[i]);}printf(\n);return 0;
}方法三颠倒数组
void reverse(int* a, int begin, int end)
{while (begin end){int tmp a[begin];a[begin] a[end];a[end] tmp;begin;--end;}
}
void func3(int* a, int sz, int k)
{reverse(a, 0, sz - k - 1);reverse(a, sz-k, sz- 1);reverse(a, 0, sz - 1);
}
int main()
{int k 0;scanf(%d, k);int arr[9] { 1,2,3,4,5,6,7,8,9 };int sz sizeof(arr) / sizeof(arr[0]);k % sz;//方法三func3(arr, sz, k);for (int i 0; i sz;i){printf(%d , arr[i]);}printf(\n);return 0;
}
