【数据结构】复杂度讲解

您所在的位置：网站首页 › 线性结构的数据元素之间存在什么关系 › 【数据结构】复杂度讲解

【数据结构】复杂度讲解

2023-04-19 22:44| 来源: 网络整理| 查看: 265

时间复杂度与空间复杂度：：什么是数据结构?

数据结构中是计算机存储,组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合.

什么是算法？

算法是定义良好的计算过程,它取一个或一组的值为输入,并产生一个或一组值作为输出.简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果.

例如：数据结构是在内存中管理数据——增删查改数据库是在磁盘中管理数据——增删查改

B树用到二分查找算法去重要用到搜索树

1.算法效率

算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源,因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度. 时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间在计算机发展的早期,计算机的存储容量很小,所以对空间复杂度很是在乎,但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度,所以我们如今已经不需要再特别关注一个算法的空间复杂度. 摩尔定律:集成电路上可以容纳的晶体管数目在大约每经过18个月便会增加一倍.

2.时间复杂度

时间复杂度的概念：

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间. 一个算法执行所耗费的时间,从理论上来说是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道. 但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式. 一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作执行次数,为算法的时间复杂度. 即:找到某条语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度.

void Func1(int N) { int count = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++i) { ++count; } } for (int k = 0; k < 2 * N; ++k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count); } 时间复杂度为:O(N^2) 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); } 时间复杂度为: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); } 时间复杂度为:O(M+N) 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(N^2) void Fun4(int N) { int count = 0; for (int k = 0; k < 100; ++k) { ++count; } printf("%d\n", count); } 时间复杂度为:O(1)

大O的渐进表示法：大O符号是用于描述函数渐进行为的数学符号. 推导大O渐进表示法： 1.用常数1取代运行时间中的所有加法常数. 2.在修改后的运行次数函数中,只保留最高阶项. 3.如果最高阶系数存在且不是1,则去掉与这个项目相乘的常数,得到的结果就是大O阶.

算法的时间复杂度存在最好,最坏和平均情况：最坏情况:任意输入规模的最大运行次数(上界) 平均情况:任意输入规模的期望运行次数最好情况:任意输入规模的最小运行次数(下界) 例如:在一个长度为N的数组中搜索一个数据x 最好情况:1次找到最坏情况:N次找到平均情况:N/2次找到在实际情况中关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n - 1; //[begin,end] begin和end是左闭右闭区间,因此有=号 while (begin > 1); if (a[mid] < x) begin = mid + 1; else if (a[mid] > x) end = mid - 1; else return mid; } return -1; } 二分查找的最好情况是O(1) 二分查找的最坏情况是找不到时间复杂度为O(logN) 每查找一次查找区间个数减少一半(除2) N/2/2/2.../2 = 1 longlong Fac(size_t N) { if (1 == N) return 1; return Fac(N - 1) * N; } 时间复杂度为O(N) longlong Fib(size_t N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); } 时间复杂度为O(2^N) longlong Fib(size_t N) { if (N < 3) return 1; longlong f1 = 1, f2 = 1, f3; for (size_t i = 3; i 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) 计算Fac的空间复杂度 longlong Fac(size_t N) { if (N == 0) return 1; return Fac(N - 1) * N; } 空间复杂度为O(N) 每个函数栈帧是常数个有N+1个Fac栈帧计算Fib的空间复杂度 longlong Fib(size_t N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); } 空间复杂度为O(N)4.常见时间复杂度以及复杂度OJ练习

一般算法常见的复杂度如下：

5201314

O(1)

常数阶

3n+4

O(n)

线性阶

3n^2+4n+5

O(n^2)

平方阶

3log(2)n+4

O(logn)

对数阶

2n+3nlog(2)n+14

O(n*logn)

nlogn阶

n^3+2n^2+4n+6

O(n^3)

立方阶

2^n

O(2^n)

指数阶

复杂度的OJ练习：

消失的数字：

int missingNumber(int* nums, int numSize) { int x = 0; for (int i = 0; i < numSize; ++i) { x ^= nums[i]; } for (int j = 0; i < numSize + 1; ++j) { x ^= j; } return x; }

旋转数组：

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 rotate(int* num, int numSize, int k) { if (k > numSize) k %= numSize; reverse(nums, 0, numsSize - k - 1); reverse(nums, numSize - k, numsSize - 1); reverse(nums, 0, numsSize - 1); }

【本文地址】

【数据结构】复杂度讲解

【数据结构】复杂度讲解

今日新闻

推荐新闻