品牌网站建设收费标准,黄埔区网站建设,seo优化推广公司,国内产品网站1688目录
一、基本概念
二、时间复杂度
【2.1】时间复杂度概念
【2.2】大O的渐进表示法
【2.3】举例时间复杂度计算
三、空间复杂度 一、基本概念
数据结构#xff1a;相互之间存在一种或者多种特定关系的数据元素的集合。在逻辑上可以分为线性结构#xff0c;散列结构、树…目录
一、基本概念
二、时间复杂度
【2.1】时间复杂度概念
【2.2】大O的渐进表示法
【2.3】举例时间复杂度计算
三、空间复杂度 一、基本概念
数据结构相互之间存在一种或者多种特定关系的数据元素的集合。在逻辑上可以分为线性结构散列结构、树形结构图形结构等等。
算法求解具体问题的步骤描述代码上表现出来是解决特定问题的一组有限的指令序列。
算法复杂度时间和空间复杂度衡量算法效率算法在执行过程中随着数据规模n的增长算法执行所花费的时间和空间的增长速度。
常见的时间复杂度
表达式大O表示法方程5201314O(1)常数阶3n4O(n)线性阶3n^24n5O(n^2)平方阶3log(2)n4O(logn)对数阶2n3nlog(2)n14O(nlogn)nLogn阶n^32n^24n6O(n^3)立方阶2^nO(2^n)指数阶
常见算法的时间复杂度关系O(1) O(logn) O(n) O(nlogn) O(n^2) O(2^n) O(n!) O(n^n)
【复杂度指标对比】 【创建的数据结构算法的复杂度】
大O计法应用示例O(1)数组随机访问、哈希表O(logn)二分搜索、二叉堆调整、AVL、红黑树查找O(n)线性搜索O(nlogn)堆排序、快速排序、归并排序O(n^2)冒泡排序、选择排序、插入排序O(2^n)子集树O(n!)排列树
二、时间复杂度
【2.1】时间复杂度概念 时间复杂度的定义在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗 是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。 即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。
// 请计算一下Func1中count语句总共执行了多少次
void Func1(int N)
{int count 0;for (int i 0; i N; i) // 循环次数为N^2{for (int j 0; j N; j){count;}}for (int i 0; i 2 * N; i) // 循环次数为2 * N{count;}int M 10;while (M--) // 循环次数为10{count;}printf(%d\n, count);
}
// Func1 执行的基本操作次数 F(N) (N^2) (2 * N) 10
// 比如N 10 F(N) 130
// 比如N 100 F(N) 10210
// 比如N 1000 F(N) 1002010
// 上面N越大后面两项对整个表达式的影响是越来越小的
// 实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。
// 最终以大概的次数上面代码的时间复杂度是N^2
【2.2】大O的渐进表示法
大O符号Big O notation是用于描述函数渐进行为的数学符号。
【推导大O阶方法】 用常数1取代运行时间中的所有加法常数O1并不代表是1次而是代表是常数次。 在修改后的运行次数函数中只保留最高阶项。 如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。
【使用大O的渐进表示法以后在推到一下Func1的时间复杂度为】
// Func1 执行的基本操作次数 F(N) (N^2) (2 * N) 10
// 比如N 10 F(N) 130
// 比如N 100 F(N) 10210
// 比如N 1000 F(N) 1002010
// 结果去掉(2*N)去掉(10) - 时间复杂度是N^2 通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数另外有些算法的时间复杂度存在最好、平均和最坏情况 最坏情况任意输入规模的最大运行次数(上界)。 平均情况任意输入规模的期望运行次数。 最好情况任意输入规模的最小运行次数(下界)。 例如在一个长度为N数组中搜索一个数据x。 最好情况1次找到。 最坏情况N次找到。 平均情况N/2次找到。
在实际中一般情况关注的是算法的最坏运行情况
【2.3】举例时间复杂度计算
【实例】
// 计算Func2的时间复杂度
void Func2(int N)
{int count 0;for (int k 0; k 2 * N; k)// 循环次数2 * N{count;}int M 10;while (M--) // // 循环次数10{count;}printf(%d\n, count);
}
// 正常为(2 * N) 10
// 在此10 影响不大 2为固定值影响不大影响时间复杂度的是N
// 以大O表示法O(N)
【实例】
// 计算Func3的时间复杂度
void Func3(int N, int M)
{int count 0;for (int k 0; k M; k) // 循环次数为M次{count;}for (int k 0; k N; k) // 循环次数为N次{count;}printf(%d\n, count);
}
// 正常为M N
// 在此M 和 N 的准确值都是不知道的所以都算在时间复杂度成员里
// 以大O表示法O(M N)
【实例】
// 计算Func4的时间复杂度
void Func4(int N)
{int count 0;for (int k 0; k 100; k) // 循环次数为100次{count;}printf(%d\n, count);
}
// 正常为100次
// 在此N 没有参与任何东西
// 以大O表示法O(1)
【实例】
// 计算strchr的时间复杂度
const char * strchr(const char * str, int character); // O(N)
【实例】
// 计算BubbleSort的时间复杂度
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end) // 循环次数为等差数列{ // N-1 N-2 N-3 N-4.... - 123N-1 N(N-1)/2int 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;}
}
// 正常为
// 在此实例5基本操作执行最好N次最坏执行了(N*(N1)/2次通过推导大O阶方法时间复杂度一般看最坏时间复杂度为 O(N ^ 2)
// 以大O表示法O(N^2)这是最坏的情况加
// 最好的情况下是O(N)
【实例】
// 计算BinarySearch的时间复杂度
int BinarySearch(int* a, int n, int x) // O(N * Log(2)n)
{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 - 1;elsereturn mid;}return -1;
}
【实例】
// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N) // O(N)
{if (0 N)return 1;return Fac(N - 1)*N;
}
【实例】
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N) // O(2^N) - 斐波那契数相当于是一个很垃圾的算法
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
} // 优化
long long Fac(size_t N)
{if (N 3)return 1;long long f1 1, f2 1, f3;for (size_t i 3; i N; i){f3 f1 f2;// 迭代f1 f2;f2 f3;}return f3;
}
三、空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
【实例】
// 计算BubbleSort的空间复杂度
void BubbleSort(int* a, int n) // 常数个额外空间所以空间复杂度为 O(1)
{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;}
}
【实例】
// 计算Fibonacci的空间复杂度
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n) // 动态开辟了N个空间空间复杂度为 O(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;
}
【实例】
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N) // 递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间。空间复杂度为O(N)
{if (N 0)return 1;return Fac(N - 1) * N;
}
