商业网站建设设计,网络设计过程,中国建材人才网,盱眙住房和城乡建设局网站在计算机科学中#xff0c;算法的效率是一个重要的概念。算法的效率可以通过复杂度来度量#xff0c;其中包括时间复杂度和空间复杂度。 了解算法的复杂度对于程序员来说非常重要。在解决实际问题时#xff0c;我们需要选择合适的算法来保证程序的性能和效率。因此#xff… 在计算机科学中算法的效率是一个重要的概念。算法的效率可以通过复杂度来度量其中包括时间复杂度和空间复杂度。 了解算法的复杂度对于程序员来说非常重要。在解决实际问题时我们需要选择合适的算法来保证程序的性能和效率。因此在学习和实践中掌握算法的复杂度分析方法是必不可少的。 本篇博客将详细探讨算法复杂度相关知识并将通过一些与复杂度相关的OJ题目来进一步讨论算法的复杂度和效率。这些题目将涵盖不同的算法思想和实际应用场景帮助读者加深对复杂度的理解并提供实际的编程练习机会。希望通过本博客的阅读读者能够掌握算法的复杂度分析方法提升自己的编程能力和解决问题的能力。 个人主页Oldinjuly的个人主页 收录专栏数据结构 欢迎各位点赞收藏⭐关注❤️ 目录
1.算法效率
2.时间复杂度
2.1 时间复杂度的概念
2.2 大O的渐进表示法
2.3 常见的时间复杂度计算
3.空间复杂度
4.复杂度的oj题
4.1 消失的数字
4.2 旋转数组 1.算法效率
long long Fib(int N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}斐波那契数列的递归实现方式非常简洁但简洁一定好吗那该如何衡量其好与坏呢
算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏一般 是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
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);}
}Func1 执行的基本操作次数 F(N)N^22*N10 N 10 F(N) 130 N 100 F(N) 10210 N 1000 F(N) 1002010 实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。
2.2 大O的渐进表示法
大O符号Big O notation是用于描述函数渐进行为的数学符号。 推导大O阶方法
用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中只保留最高阶项。如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后Func1的时间复杂度为O(N^2) N 10 F(N) 100 N 100 F(N) 10000 N 1000 F(N) 1000000
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况 最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界) 例如在一个长度为N数组中搜索一个数据x 最好情况1次找到 最坏情况N次找到 平均情况N/2次找到 在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N)
2.3 常见的时间复杂度计算
示例1
2*N10 -- O(N)
// 计算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);
}
示例2
M和N的影响一样大O(MN)
MN:O(M)
NM:O(N)
// 计算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);
}示例3
常数次100 -- O(1)
// 计算Func4的时间复杂度
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}示例4
O(N)
// 计算strchr的时间复杂度
const char* strchr(const char* str, int character);示例5
研究最坏情况就是每趟冒泡都要彻底交换也就是完全逆序的情况。
交换次数n-1(n-2)...1
O(N^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;}
}示例6
区间数据个数N--N/2--N/4--...--1
最坏情况N/2/2/2.../2/21(没找到或者二分到最后才找到)
2^xN -- xlogN查找次数
O(logN)
注意只有以2为底的才能写成logN其他的按照要求写。
// 计算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 mid 1;else if (a[mid] x)end mid;elsereturn mid;}return -1;
}关于查找算法的补充 暴力查找O(N) 二分查找O(logN)本身的查找效率很高但是前置条件是有序想法很美好但是现实很残酷所以这是个纸上谈兵的算法后面我们要学其他的高阶数据结构来进行查找如AVL树红黑树B树他们不需要有序但是时间复杂度依然在O(logN)。 示例7
递归
O(N)
// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}示例8
O(2^N)
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
} 注意这种双路递归的时间复杂度是指数级别的效率是非常低的但是并不会轻易导致栈溢出空间是可以重复使用的。
所以这种代码不能轻易写出要慎重考虑。
3.空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时额外占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
示例1
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;}
}示例2
O(N)
// 计算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;
}示例3
递归调用N次开辟了N个栈帧。
O(N)
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if(N 0)return 1;return Fac(N-1)*N;
}示例4
O(N)
空间是可以重复利用的时间是不断累加的。
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}递归的缺陷 除了双路递归效率和循环不会差太多的但是递归太深的话会有栈溢出的风险。 4.复杂度的oj题
4.1 消失的数字
方法1排序然后再找 时间复杂度O(logN*N) 空间复杂度O(1)方法2计数 时间复杂度O(N) 空间复杂度O(N)方法30到N等差数列计算结果-数组中所有的值结果是消失的数字 时间复杂度O(N) 空间复杂度O1方法4: 异或^的奇妙用法时间复杂度O(N) 空间复杂度O1
int missingNumber(int* nums, int numsSize)
{int ret0;int i0;for(i0;inumsSize;i){ret^nums[i];}for(i0;inumsSize;i){ret^i;}return ret;
}4.2 旋转数组
方法一每次右旋一次累计旋转K%N次。
时间复杂度 O(N^2) 空间复杂度 O(1) 方法二开辟空间
时间复杂度O(N) 空间复杂度O(N)
方法三三次旋转这个有点难想
时间复杂度O(N) 空间复杂度O1
