五金网站建设,客源引流推广app,播州区住房城乡建设路的网站,linux做网站网络课堂1、时间复杂度和空间复杂度
#xff08;1#xff09;时间复杂度、空间复杂度是什么#xff1f;
算法效率分析分为两种#xff1a;第一种是时间效率#xff0c;第二种是空间效率。时间效率被称为时间复杂度#xff0c;空间效率被称作空间复杂度时间复杂度主要衡量的是一…1、时间复杂度和空间复杂度
1时间复杂度、空间复杂度是什么
算法效率分析分为两种第一种是时间效率第二种是空间效率。时间效率被称为时间复杂度空间效率被称作空间复杂度时间复杂度主要衡量的是一个算法的运行速度而空间复杂度主要衡量一个算法所需要的额外空间在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度如今更加考虑时间复杂度
2时间复杂度的计算
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 * N 2 * N 10①代码解析
实际的们计算时间复杂度的时候不用计算如此精确的执行次数于是这里我们使用大O渐进表示法时间复杂度不算时间算次数
②大O表示法
是用于描述函数渐进行为的数学符号
③推导方法
用常数1取代运行时间中的所有加法常数在修改后的运行函数中只保留最高阶项如果高阶项存在且不是1则去除于这个项目相乘的常数
④最好、平均、最坏情况
最好情况任意输入规模的最大运行次数上界平均情况任意输入规模的期望运行次数最好情况任意输入规模的最小运行次数下界
⑤推导例子
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);
}
//2 * N 10 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 NO(M N)
//如果M远大于NO(M)
//如果M、N相差不大O(2 * M)/O(2 * N)O(M)/O(N)void Func4(int N)//N没有用到时间复杂度与N无关
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}
//100O(1)反过来就说明输入数据了常数次//计算strchr的时间复杂度
const char * strchr ( const char * str, char character )
{while(*str ! \0){if(*str character)return str;str;}return NULL;
}
//需要分情况最坏、平均、最好假设字符串长度为N
//最坏的没有找到或者在最后找到O(N)
//平均就是O(N / 2)
//最坏就是O(1)
//当要分情况的时候要用最坏的情况表示因此最终结果就是O(N) // 计算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;}
}
//这个也要分情况
//第一次冒泡N次也可以理解为N - 1的
//第二次冒泡N - 1次
//……
//第N次冒泡1次
//和为((1 N) * N) / 2
//因此最坏情况O(N^2)// 计算BinarySearch的时间复杂度二分查找法
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n;while (begin end){int mid begin ((end-begin) 1);//求平均值if (a[mid] x){ begin mid1;}else if (a[mid] x){end mid;}else{return mid;}}return -1;
}
//这个也要分情况
//O(log(2)N)简写为log(N)最好不要写lg(N)尽管有的地方会这样写详细解说在下面// 计算阶乘递归Factorial的时间复杂度
long long Factorial(size_t N)
{return N 2 ? N : Factorial(N-1) * N;
}
//Factorial(10)
//Factorial(9) * 10
//Factorial(8) * 9
//……
//Factorial(1) * 2
递归了N次每次就是O(1)整体就是O(N)
//如果假设递归内用的是循环语句for(int i 0; i N; i);则每次是O(N)整体就是O(N^2)⑥常见的时间复杂度对比
O(1) O(logN) O(N) O(N^2)
3空间复杂度的计算
// 计算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;}
}
//标粗的地方占用了变量即5O(1)
//注意时间是累积的空间是不累积的因为重复利用了一个空间①代码解析
实际的们计算空间复杂度的时候也不用计算如此精确的空间只需要知道大概的执行次数即可于是这里我们也同样使用大O渐进表示法空间复杂度不算空间算变量个数
②大O表示法
是用于描述函数渐进行为的数学符号
③推导方法
用常数1取代运行时间中的所有加法常数在修改后的运行函数中只保留最高阶项如果高阶项存在且不是1则去除于这个项目相乘的常数
④推导例子
// 计算Fibonacci的空间复杂度斐波那契数列
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;
}
//O(N 6)O(N)
//虽然大部分算法的空间复杂度都是O(1)// 计算阶乘递归Factorial的空间复杂度
long long Factorial(size_t N)
{return N 2 ? N : Factorial(N - 1) * N;
}
//递归调用了n层每次调用建立一个栈帧每次使用了常数O(1)整体就是O(N)2、有关的练习题目
1面试题 17.04. 消失的数字 - 力扣LeetCode
//思路一
int missingNumber(int* nums, int numsSize)
{int add_1 0;int add_2 0;add_1 ( (0 numsSize) * (numsSize 1) ) / 2;for(int i 0; i numsSize; i){add_2 nums[i];}return add_1 - add_2;
}//思路二
int missingNumber(int* nums, int numsSize)
{int x 0;int i 0;for(i 0; i numsSize; i)//用for循环求出数组nums元素的异或和{x ^ nums[i];}for(i 0; i numsSize 1; i)//运用异或的性质a^a0来找出消失的数字{x ^ i;}return x;
}2189. 轮转数组 - 力扣LeetCode
//思路一
void rotate(int* nums, int numsSize, int k)
{while(k--){int tmp nums[numsSize - 1];//保留最后一个数字for(int end numsSize - 2; end 0; --end)//开始将最后一个数字前面的所有数字后移{nums[end 1] nums[end];}nums[0] tmp;}
}
//但是超出了时间限制//思路二
void Reverse(int* nums, int left, int right)
{while(left right)//奇数个会相等偶数个会错开{int tmp nums[left];nums[left] nums[right];nums[right] tmp;left;--right;}
}
void rotate(int* nums, int numsSize, int k)
{if(k numsSize)//防止k大于数组大小例如7个元素旋转13次和6次等价{k % numsSize;}Reverse(nums, numsSize - k, numsSize - 1);//后半部分Reverse(nums, 0, numsSize - k - 1);//前半部分Reverse(nums, 0, numsSize - 1);
}
