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

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

时间:2024-09-04 21:24:45浏览次数:13  
标签:numsSize nums int 复杂度 long 空间 数据结构

1、时间复杂度

1.1 大O渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号。

推导大O阶方法:

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

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

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

另外有些算法的时间复杂度存在最好、平均和最坏情况,在实际中一般情况关注的是算法的最坏运行情况。

 1.2 常见时间复杂度计算举例

1.2.1 计算strchr的时间复杂度

const char * strchr ( const char * str, int character );

1.2.2 计算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;
        else
            return mid;
    }
    return -1;
}

1.2.3 计算斐波那契递归Fib的时间复杂度

long long Fib(size_t N)
{
    if(N < 3)
        return 1;

    return Fib(N-1) + Fib(N-2);
}

解析:

第一题:

strchr找到字符串中第一个出现的字符

执行最好1次,最坏N次,时间复杂度一般看最坏,所以时间复杂度为 O(N)

 第二题:

  • 初始搜索空间:一开始,搜索范围包含整个数组,即 n 个元素。

  • 每次迭代:在每轮循环中,算法都会计算中间位置 mid ,并将搜索空间减半。

  • 搜索空间的减少速率:由于每次迭代都会将搜索范围缩小一半,搜索空间的大小经过一次迭代后变为原来的一半。因此,经过 k 次迭代后,搜索空间的大小变为 n/2^{k}

  • 终止条件:当搜索空间缩小到只剩下一个元素或没有元素时,循环终止。此时, n/2^{k} = 1,即 2^{k} = n。将等式两边取对数,得到 k = log_{2}(n)。(这里用到了对数函数的知识: a^{x} = N(a>0,且a≠1),记作 x = \log_{a}N, )

因此,二分查找的总体时间复杂度为 O(log⁡ n)。这里的对数是以2为底的,但在大O表示法中,底数通常被省略,因为不同底数的对数函数相差一个常数倍数,而大O表示法忽略常数因子和低阶项。 

 第三题:

 所以时间复杂度为 O(2^{N})

 2、空间复杂度

空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度

空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法

注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

2.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.2 计算Fibonacci的空间复杂度

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

2.3 计算阶乘递归Fac的空间复杂度

long long Fac(size_t N)
{
    if(N == 0)
        return 1;

    return Fac(N-1)*N;
}

解析:

第一题:使用了常数个额外空间,所以空间复杂度为 O(1)

第二题:动态开辟了N个空间,空间复杂度为 O(N)

第三题:递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间(由于没有额外的局部变量,主要占用的是参数和返回值)。所以空间复杂度为O(N)

3、复杂度练习

3.1 消失的数字

面试题 17.04. 消失的数字 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/missing-number-lcci/description/

//方法一:异或,时间复杂度为O(N)
int missingNumber(int* nums, int numsSize) 
{
	int x = 0;

	//第一次for循环
	for (int i = 0; i < numsSize; i++)
	{
		x ^= nums[numsSize];
	}

	//第二次for循环
	for (int i = 0; i < numsSize + 1; i++)
	{
		x ^= i;
	}

	return x;
}

我们拿[9,6,4,2,3,5,7,0,1]举例:(numsSize = 9)

第一次for循环:0^9^6^4^2^3^5^7^0^1

第二次for循环:上一次的结果^0^1^2^3^4^5^6^7^8^9

因为异或的规则是:两个相同的数字异或结果为0,0异或上任何数都为0,所以最后的结果就是只出现了一次的8。

//方法二:0-N等差数列公式计算,减数组中的值,时间复杂度为O(N)
int missingNumber(int* nums, int numsSize) 
{
	int x = (1 + numsSize) * numsSize / 2;
	for (int i = 0; i < numsSize; i++)
	{
		x -= nums[i];
	}

	return x;
}

我们拿[9,6,4,2,3,5,7,0,1]举例:(numsSize = 9) 

x = (1+9)*9/2

for循环中:x-9-6-4-2-3-5-7-0-1,结果为8

 3.2 轮换数组

189. 轮转数组 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/rotate-array/

//方法一:三段逆置,时间复杂度O(N),空间复杂度O(1)
void reverse(int* a, int left, int right)
{
	while (left < right)
	{
		int tmp = a[left];
		a[left] = a[right];
		a[right] = tmp;
		left++;
		right--;
	}
}

void rotate(int* nums, int numsSize, int k) 
{
	if (k > numsSize)
		k %= numsSize;
	reverse(nums, 0, numsSize - k - 1);
	reverse(nums, numsSize - k, numsSize - 1);
	reverse(nums, 0, numsSize - 1);
}

我们拿nums = [1,2,3,4,5,6,7], k = 3举例:

第一次逆置:4,3,2,1,5,6,7

第二次逆置:4,3,2,1,7,6,5

第三次逆置:5,6,7,1,2,3,4

//方法二:以空间换时间时间复杂度O(N),空间复杂度O(N)
void rotate(int* nums, int numsSize, int k) 
{
	if (k > numsSize)
		k %= numsSize;

	int* tmp = (int*)malloc(sizeof(int) * numsSize);
	memcpy(tmp, nums + numsSize - k, sizeof(int) * k);
	memcpy(tmp + k, nums, sizeof(int) * (numsSize - k));
	memcpy(nums, tmp, sizeof(int) * numsSize);
	free(tmp);
	tmp = NULL;
}

 我们拿nums = [1,2,3,4,5,6,7], k = 3举例:

第一次memcpy:tmp为5,6,7

第二次memcpy:tmp为5,6,7,1,2,3,4

第三次memcpy:nums为5,6,7,1,2,3,4

标签:numsSize,nums,int,复杂度,long,空间,数据结构
From: https://blog.csdn.net/Lumos_yyyx/article/details/141872408

相关文章

  • 54.《数据结构绪论处解》
    结构和算法为程序的核心所在先谈数据和信息的关系之前计基中背诵理解的数据是信息的具体表现形式数据是信息的载体信息的符号化是数据是数据加工后的结果为了弄清五个XX概念我最烦的就是xiajiba的概念数据数据元素数据对象数据类型数据结构废话不多说上图语......
  • Linux-01-虚拟网络、网络命名空间
    虚拟网络    首先Linux具有丰富的虚拟网络功能,我们先简要介绍几个常用的虚拟网络接口类型:1.Bridge网桥        LinuxBridge网桥的行为类似于网络交换机。它在与其连接的接口之间转发数据包。它通常用于在路由器、网关上或在主机上的虚拟机和网络命名空间......
  • 数据结构--链表
    单向链表链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。相较于数组,链表有以下优点:逻辑结构(1)链表采用动态内存分配的方式,在内存中不连续(2)支持动态增加或者删除元素(3)需要时可以使用malloc或者new来申请内存,不用......
  • 算法与数据结构——AVL树(平衡二叉搜索树)
    AVL树在“二叉搜索树”章节提到,在多次插入和删除操作后,二叉搜索树可能退化为链表。在这种情况下,所有操作的时间复杂度将从O(logn)劣化为O(n)。如下图,经过两次删除节点操作,这棵二叉搜索树便会退化为链表再例如,下图所示的完美二叉树中插入两个节点后,树将严重向左倾斜,查找操作的......
  • 芯片闪存(FLASH)空间不够报错——.\Objects\SL_DEMO.axf: Error: L6406E: No space in
    目录问题描述:问题解决:问题分析:解决方法:1,2,问题描述:当出现这种报错的时候:.\Objects\SL_DEMO.axf:Error:L6406E:Nospaceinexecutionregionswith.ANYselectormatchingdrv_iap.o(i.EraseFlashSector).。是由于芯片闪存(FLASH)空间不够导致的问题解决:问题分析......
  • 数据结构和算法
    数据结构和算法数据结构数组(Array):一种线性数据结构,可以存储相同类型的元素,支持基于索引的快速访问。链表(LinkedList):由一系列节点组成,每个节点包含数据部分和指向下一个节点的指针。栈(Stack):遵循后进先出(LIFO)原则的线性数据结构,只能在一端(栈顶)进行添加或删除操作。队列(Queue):......
  • PART1-Oracle关系数据结构-分区、视图以及其他的对象
    4.分区、视图与其他对象4.1.分区概述分区允许您将非常大的表和索引分解成更小、更易于管理的部分,称为分区。每个分区是一个独立的对象,有自己的名称,并且可以选择拥有自己的存储特性。为了说明分区的概念,假设一个人力资源经理有一个大盒子,里面装着员工文件夹。每个文件夹都列出......
  • 【数据结构和算法实践-树-LeetCode100-判断是否是相同的树】
    数据结构和算法实践-树-LeetCode100-判断是否是相同的树题目MyThought代码示例JAVA-8题目给你两棵二叉树的根节点p和q,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。示例输入:p=[1,2,3],q=[1,2......
  • 【数据结构和算法实践-链表-LeetCode23-合并K个有序数组】
    合并K个有序数组题目MyThought代码示例JAVA-8题目合并K个有序数组MyThought一、将ListNode放入PriorityQueue中1.1、设置PriorityQueue的比较器规则1.2、将ListNode[]放入priorityQueue二、再将数据依次弹出放到ListNode中代码示例JAVA-8publicListNod......
  • Python 默认列表(Default List):一种灵活的数据结构
    Python中的默认列表(DefaultList)是一种特殊的数据结构,它允许我们创建一个包含特定元素类型的列表,并在需要时动态地添加或删除元素。这种灵活性使得默认列表成为了处理一些不确定或变化的数据的有力工具。创建列表时指定元素类型在Python中,我们可以在创建列表时指定元素类型,如果......