首页 > 其他分享 >【数据结构】时间复杂度与空间复杂度概念

【数据结构】时间复杂度与空间复杂度概念

时间:2022-10-22 13:03:33浏览次数:52  
标签:count int 复杂度 ++ long 概念 fibArray 数据结构

1.时间复杂度

1.什么是时间复杂度

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

单看概念似乎有点难以理解,我们以实例来讲解一下

void Func(int n)
{
int count = 0;
for (int i = 0; i < n; i++)
{
count++;
}
}

 在这个函数之中count++在循环中执行了n次,所以它的时间复杂度就是n

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);
}

面的这段程序count++操作执行了N^2+2*N+10次,它的时间复杂度就是N^2+2*N+10

2.大O的渐进表示法

我们在题目或者课本上看到的时间复杂度说明基本都是使用的大O的渐进表示法

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这 里我们使用大O的渐进表示法。

我们假设N趋近于无穷大那么,很多项的影响将会接近于没有。我们假设一个程序需要执行的操作数为2*N^2+2*N+10,如果N趋近于无穷大那个2N和10的影响将会越来越小接近于没有。

1、用常数1取代运行时间中的所有加法常数。

2*N^2+2*N+1(如果只有常数项,那么它的时间复杂度就是O(1))

2、在修改后的运行次数函数中,只保留最高阶项。

2*N^2

3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

N^2

所以这个时间复杂度就是O(N^2)

3.空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践 复杂度类似,也使用大O渐进表示法。

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(1)

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 ;
}

我们动态开辟了n个空间复杂度为O(n)

long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}

函数在每次调用时都会在栈上开辟空间,这里我们递归了n次,开辟了n个个栈帧所以空间复杂度也是O(N)

标签:count,int,复杂度,++,long,概念,fibArray,数据结构
From: https://blog.51cto.com/u_15572441/5785800

相关文章

  • 小孩的游戏 - 2021数据结构 排序和选择实验题
    小孩的游戏-2021数据结构排序和选择实验题pre做都做了,干脆发上来算了:D题目分析算法与数据结构实验题5.18小孩的游戏★实验任务一群小孩子在玩游戏,游戏......
  • JavaScript实现数据结构 -- 集合
    集合集合是一种无序且唯一的数据结构,在ES6中有集合Set。集合的常用操作去重使用Set结合展开运算符实现数组去重。判断元素是非在集合中使用Set的has方法判断元素是......
  • JavaScript实现数据结构 -- 字典
    字典字典与集合类似,也是一种存储唯一值的数据结构,字典以键值对的形式进行存储,在ES6中有字典Map。字典的常用操作增使用set()方法可以向字典中添加新成员,可连续添加。......
  • 数据结构—案例二
    案例1:一元多项式的运算【案例分析】已知一元多项式可以抽象成一个线性表。在计算机中,我们可以采用数组来表示一元多项式的线性表。利用数组p表示:数组中每个分量p[i]表示......
  • 数据结构—线性表的应用
    一、线性表的合并例1  求解一般集合的并集问题【问题描述】已知两个集合A和B,现要求一个新的集合A=AUB。例如,设            A=(7,5,3,11)      ......
  • 数据结构—顺序表和链表的比较
    单链表、循环链表和双向链表的时间效率比较 链式存储结构的优点:结点空间可以动态申请和释放数据元素的逻辑次序靠结点的指针来指示,插入和删除时不需要移动数据元素......
  • 数据结构—线性表的链式表示和实现
    一、链表概念链式存储结构:结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻。线性表的链式表示又称为非顺序映像或链式映像。用一组物理位置任意的......
  • python的高级特性-迭代概念
    迭代Python内置的enumerate函数可以把一个list变成索引-元素对,这样就可以在for循环中同时迭代索引和元素本身>>>fori,valueinenumerate(['A','B','C']):...prin......
  • SaaS平台和服务的概念【杭州多测师】
    SaaS就是Software-as-a-service,通俗就是软件即服务,SaaS服务提供商会给企业和公司提供基础网络设施以及软件、平台服务,负责前期的搭建实施以及后期维稳服务,客户的服务可以按......
  • 【数据结构/C语言】有序单链表L1、L2合并
    1.根据输入的n和n个递增的有序数据建立一个带头结点的有序单链表L1,并输出有序链表中各元素值;2.根据输入的m和m个递增的有序数据建立一个带头结点的有序单链表L2,并输出有......