网站ui设计报价单,深圳网站建设公司市场,快站优惠券,如何开发网站自己做站长目录 一、如何衡量一个算法的好坏#xff1f;二、时间复杂度1. 时间复杂度的计算方法2. 时间复杂度习题 三、空间复杂度1. 空间复杂度的计算方法2. 空间复杂度习题 四、常见复杂度对比五、复杂度oj题1. 消失的数字2. 轮转数组 一、如何衡量一个算法的好坏#xff1f;
如果一… 目录 一、如何衡量一个算法的好坏二、时间复杂度1. 时间复杂度的计算方法2. 时间复杂度习题 三、空间复杂度1. 空间复杂度的计算方法2. 空间复杂度习题 四、常见复杂度对比五、复杂度oj题1. 消失的数字2. 轮转数组 一、如何衡量一个算法的好坏
如果一个算法运行速度快且消耗内存少那么该算法一定是一个效率高的好算法。那么如何计算一个算法的速度和消耗的内存呢通常我们使用时间复杂度和空间复杂度来衡量一个算法的好坏并且使用大O表示法来表示。
二、时间复杂度
1. 时间复杂度的计算方法
一、确定基本操作 首先明确算法中的基本操作。基本操作通常是指算法中执行次数最多或者对时间影响最大的操作。例如在一个循环中循环体的执行次数通常是基本操作在排序算法中比较操作和交换操作可能是基本操作。
二、分析基本操作的执行次数与问题规模的关系
用问题规模的变量来表示基本操作的执行次数。例如如果算法是对一个长度为 n 的数组进行操作那么问题规模通常用 n 表示。分析算法的结构确定基本操作的执行次数与问题规模之间的关系。这可能需要对算法进行逐步分析考虑不同的情况和分支。
三、用大 O 记号表示时间复杂度
忽略低阶项和系数。在表示时间复杂度时只关注最高阶项因为当问题规模足够大时低阶项和系数对时间的影响相对较小。根据基本操作的执行次数与问题规模的关系常见的时间复杂度级别有常数阶 O (1)、对数阶 O (log n)、线性阶 O (n)、线性对数阶 O (n log n)、平方阶 O (n²) 等。
用作者的话来说就是有循环就计算整个算法中循环语句的执行次数没有循环就计算整个算法所执行的所有语句数。然后用问题的规模的变量把这个计算结果表示出来最后使用大O表示法去掉最高项的系数只保留最高项的阶数结果就是该算法的时间复杂的大O表示法。如果该算法中有函数调用或者递归也是同样的计算方法。
2. 时间复杂度习题
例题1
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;}首先有循环就计算循环语句的执行次数n2 2n 10 其次从该函数的参数判断该算法的规模为 n 接着使用规模变量表示前面的执行次数n2 2n 10 最后使用大O表示法去掉最高阶系数只保留最高阶O(n2)
例题2 下面是一个计算前 n 项正整数之和的算法
// 计算前 n 项和
long long sum_first_n(int n)
{int i;long long sum 0;for (i 1; i n; i)sum i;// 返回return sum;
}首先有循环那么就计算循环语句的执行次数n。 然后该算法是计算前 n 项正整数的和规模变量为 n。 接着用规模变量表示前面计算的执行次数n。 最后使用大O表示法去掉最高阶系数只保留最高阶O(n)。
例题3
// 计算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 规模变量表示MN 如果题目说明 M 远大于 N则 O(M)如果 N 远大于 M则O(N)如果没有说明则 O(MN)。
例题4
// 计算Func4的时间复杂度
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}循环语句执行次数100 问题规模变量表示100 结果为常数那就是常数阶O(1)不管这个常数多大只要是一个常数那都是O(1)
例题5
// 计算strchr的时间复杂度
const char * strchr ( const char * str, int character );库函数 strchr() 的功能是在一个字符串中查找指定字符如果找到了就返回该字符的地址如果没找到就返回空指针。
那么通过计算该算法的时间复杂度并不唯一如果带查找的字符刚好在第一个那么只需要查找一次时间复杂度也就是O(1)如果带查找的字符刚好在最后一个那么需要查找 n 次时间复杂度也就是O(n)。
在这种存在最好和最坏的情况的算法中通常是取最坏的情况。那么该算法的时间复杂度就是 O(n)。
例题6 下面是一个优化过后的冒泡排序
// 计算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;}
}该冒泡排序算法也存在最好和最坏两种情况 1当待排序数组完全有序那么第一轮比较之后就会跳出循环。那么循环中 if 条件语句执行的次数为 n-1其时间复杂度也就是 O(n) 2当待排序数组完全逆序那么冒泡排序就会一直执行到结束。那么循环中 if 条件语句的执行次数为 (n-1)(n-2)…1其时间复杂度为 O(n2)
例题7 下面是一个二分查找的算法
// 计算BinarySearch的时间复杂度
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n-1;while (begin end){// 取得中间数int mid begin ((end-begin)1);// 判断if (a[mid] x)begin mid1;else if (a[mid] x)end mid;elsereturn mid;}return -1;
}二分查找是在 n 个有序的数中查找一个数而且每次查找都可以去掉一半的数也就是剩下 n/2 个数。最坏的情况就是查找到最后一个数也就是 n/2/2/2…/2 1即 2k nk log2n这个 k 也就是要查找的次数且每次查找所执行的语句也是常数所以该算法的时间复杂度就是 O(log2n)也就是上面说的对数阶。
例题8 下面是计算正整数 n 的阶乘的递归算法
// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if(0 N)return 1;return Fac(N-1)*N;
}通过计算该函数加上递归一共需要被调用 N1 次每次调用该函数执行常数条语句所以该算法的时间复杂度为 O(n)
例题9 下面是第 n 项斐波那契数列的递归算法
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}首先递归调用一次执行常数条语句那么一共递归调用多少次 如上图所示我们把缺失的项设置为 k那么递归调用的次数为20 21 22 … 2n-1 - k 2n - 1 - k相比于 2n 来说 1k 显得微不足道所以该求斐波那契第 n 项的递归算法的时间复杂度为 O(2n)
三、空间复杂度
1. 空间复杂度的计算方法
有了前面时间复杂度的计算方法那么空间复杂度的计算就要简单很多了。 1统计创建变量的个数不管是什么类型 2用问题的规模变量表示变量的总个数 3大O表示法去掉最高阶的系数只保留最高阶
2. 空间复杂度习题
习题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;}
}由于在执行算法的过程中只开辟了常数个变量end、i 和 exchange所以该算法的空间复杂度为 O(1)
习题2 下面是阶乘的递归算法
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if(N 0)return 1;return Fac(N-1)*N;
}虽然在递归的过程中没有开辟新的变量但是每次递归都需要开辟栈帧空间一共递归 n1 次开辟了 n1 个栈帧空间所以该算法的空间复杂度为 O(n)
习题3 下面是第 n 项斐波那契数列的递归算法
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}前面通过画图的方式的出该递归需要调用 2n 层级的次数那么是否需要开辟 2n 层级的函数栈桢
答案肯定不是仔细阅读代码你会发现每次递归调用函数 Fib 时它都会先调用左边的 Fib(N-1)然后再在里面调用他自己的 Fib(N-1)直到最后一次递归时它的 N-1 3 时才会返回上一层递归然后调用该层递归的 Fib(N-2)。如下图 所以该算法运行时函数栈帧消耗的最大层数为 n所以该算法的空间复杂度为 O(n)
四、常见复杂度对比 上述图片均来自比特的课件哈作者比较懒也不会画。
五、复杂度oj题
1. 消失的数字
题目描述 数组nums包含从 0 到 n 的所有整数但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在 O(n) 的时间复杂度内完成吗
注意本题相对书上原题稍作改动
示例 1 输入[3,0,1] 输出2
示例 2 输入[9,6,4,2,3,5,7,0,1] 输出8
题目OJ链接 链接: link
题目解析 1题目要求时间复杂度需要 O(n) 2三种算法
a. 计算 0 - n 的和然后减去数组的每个元素结果就是缺失的数
// 计算 0 - n 的和然后减去数组的每个元素
int find_missing_num(int *arr, int sz)
{// 计算 0-n 之和int sum (sz 1) * sz / 2;// 减去数组的每个元素int i;for (i 0; i sz; i){sum - arr[i];}// 返回return sum;
}时间复杂度 O(n) 空间复杂度 O(1)
b. 用 0 - n 与数组的每个元素异或结果就是缺失的数
int find_missing_num(int* arr, int sz)
{int result sz;int i;for (i 0; i sz; i){result ^ i ^ arr[i];}// 返回return result;
}由于循环是 0 - n-1所以 result 的初值为 sz。
时间复杂度 O(n) 空间复杂度 O(1)
c. 使用 calloc() 函数动态开辟一个大小为 n1 的 int 数组该数组用来统计 0 - n 的出现次数遍历原数组记录出现次数然后遍历次数数组出现次数为 0 的就是缺失的数。
int find_missing_num(int* arr, int sz)
{// 动态开辟次数数组int* times (int*)calloc((sz 1), sizeof(int));// 遍历原数组统计次数int i;for (i 0; i sz; i)times[arr[i]];// 遍历次数数组找缺失数for (i 0; i sz; i){if (0 times[i])break;}// 释放free(times);times NULL;// 返回return i;
}时间复杂度 O(n) 空间复杂度 O(n)
2. 轮转数组
题目描述 给定一个整数数组 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
题目OJ链接 链接: link
题目解析 1像这种旋转数组或者字符串的问题不管是右旋转还是坐旋转当旋转次数为其长度的整数倍时就会复原。也就是旋转的周期是其长度如1,2,3,4右旋转或者左旋转 4n 次后复原。所以实际的旋转次数需要对其长度取余。
2三种解法
a. 暴力求解法 就是直接一步一步旋转没有任何技巧可言
// 暴力求解法
void rotate_arr_i(int* arr, int sz, int k)
{// 实际旋转次数int n k % sz;// 旋转while (n--){// 存储尾元素int tmp arr[sz - 1];// 前面元素往后移int i;for (i sz - 1; i 0; i)arr[i] arr[i - 1];// 尾元素放开头arr[0] tmp;}
}时间复杂度 O(n2) 空间复杂度 O(1)
b. 三步逆序法三种里面最优 先计算实际旋转次数 k然后把后 k 项逆序再把前 sz-k 项逆序最后整个数组逆序就是想要的结果。
// 三步逆序法// 逆序
void reverse(int* left, int* right)
{while (left right){// 交换int tmp *left;*left *right;*right tmp;// 下一组left;--right;}
}// 三步
void rotate_arr_i(int* arr, int sz, int k)
{// 实际旋转次数k % sz;// 三步逆序reverse(arr sz - k, arr sz - 1);reverse(arr, arr sz - k - 1);reverse(arr, arr sz - 1);
}时间复杂度 O(n) 空间复杂度 O(1)
c. 额外开辟数组法 这是一个空间换时间的方法额外开辟一个大小相同的动态数组然后算出实际旋转次数 k把后 k 项放在新数组前面再把前 sz-k 项放在新数组后面最后把新数组拷贝到原数组。
// 额外开辟数组法
void rotate_arr_i(int* arr, int sz, int k)
{// 实际旋转次数k % sz;// 开辟额外数组int* tmp (int*)malloc(sizeof(int) * sz);// 把原数组旋转后的顺序拷贝到新数组int i;for (i 0; i k; i)tmp[i] arr[sz - k i];for (i 0; i sz - k; i)tmp[k - 1 i] arr[i];// 把新数组拷贝到原数组for (i 0; i sz; i)arr[i] tmp[i];// 释放额外数组free(tmp);
}时间复杂度 O(n) 空间复杂度 O(n)
