时间复杂度&&空间复杂度&&顺序表&&链表&&顺序表和链表的区别以及优缺点对比_顺序表空间复杂度

一、时间复杂度

时间复杂度 - 算法中的基本操作的执行次数，为算法的时间复杂度。
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这
里我们使用大O的渐进表示法。
推导大O阶方法：

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶

二、空间复杂度

空间复杂度 - 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度
推导方法：

1. 不考虑输入数组的，考虑的算法运行中额外开辟的空间
2. 时间是累积的，空间是不累积可以复用的
3. 递归算法的空间复杂度通常是递归的深度

三、顺序表

1.SeqList.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
静态的顺序表
//#define N 100
//struct SeqList
//{
   
//	int a[N];
//	int size;
//};

typedef int SeqDataType;

typedef struct SeqList
{
   
	SeqDataType *a;
	int size;//有效数据的个数
	int capacity;//容量空间的大小
}SeqList;

//内存中管理数据的结构增删改查的接口

//函数声明
//初始化
void SeqListInit(SeqList* pq);
//尾插
void SeqListPushBack(SeqList* pq, SeqDataType x);
//头插
void SeqListPushFront(SeqList* pq, SeqDataType x);
//指定位置插入
void SeqListInsert(SeqList* pq, size_t pos, SeqDataType x);
//头删
void SeqListPopFront(SeqList* pq);
//尾删
void SeqListPopBack(SeqList* pq);
//指定位置删除
void SeqListDelete(SeqList* pq, size_t pos);
//指定位置修改数据
void SeqListModify(SeqList* pq, size_t pos, SeqDataType x);
//打印数据
void SeqLisPrint(SeqList* pq);
//销毁
void SeqListDestory(SeqList* pq);
//增容
void SeqCheckCapacity(SeqList* pq);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

2.SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
//初始化
void SeqListInit(SeqList* pq)
{
   
	assert(pq);
	pq->a = 0;
	pq->capacity = pq->size = 0;
}

//增容
void SeqCheckCapacity(SeqList* pq)
{
   
	assert(pq);
	if (pq->size == pq->capacity)
	{
   
		int newcapacity = pq->capacity == 0 ? 4 : 2 * (pq->capacity);
		SeqDataType* newpq = realloc(pq->a, sizeof(SeqDataType) * newcapacity);
		if (newpq == NULL)
		{
   
			perror("SeqCheckCapacity");
		}
		pq->a = newpq;
		pq->capacity = newcapacity;
	}
}

//尾插
void SeqListPushBack(SeqList* pq, SeqDataType x)
{
   
	assert(pq);
	//增容
	SeqCheckCapacity(pq);
	//pq->a[pq->size] = x;
	//pq->size++;
	SeqListInsert(pq, pq->size, x);
}

//头插
void SeqListPushFront(SeqList* pq, SeqDataType x)
{
   
	assert(pq);
	//增容
	SeqCheckCapacity(pq);
	//int end = pq->size - 1;
	//while (end >= 0)
	//{
   
	//	pq->a[end + 1] = pq->a[end];
	//	end--;
	//}
	//pq->a[0] = x;
	//pq->size++;
	SeqListInsert(pq, 0, x);
}

//指定位置插入
void SeqListInsert(SeqList* pq, size_t pos, SeqDataType x)
{
   
	assert(pq);
	assert(pos <= pq->size);
	//增容
	SeqCheckCapacity(pq);
	size_t end = pq->size;
	while (end > pos)
	{
   
		pq->a[end] = pq->a[end - 1];
		end--;
	}
	pq->a[pos] <
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77