安阳百度网站制作多少钱cfensi.wordpress

安阳百度网站制作多少钱,cfensi.wordpress,青岛关键词网站排名,新余网站制作一、队列时间复杂度分析1. 链队列时间复杂度// 链队列节点 typedef struct QueueNode {int data;struct QueueNode* next; // 额外指针开销 } QueueNode;// 链队列结构 typedef struct {QueueNode* front; // 队头指针QueueNode* rear; // 队尾指针 } LinkedQueue;入队操作…一、队列时间复杂度分析1.链队列时间复杂度// 链队列节点 typedef struct QueueNode { int data; struct QueueNode* next; // 额外指针开销 } QueueNode; // 链队列结构 typedef struct { QueueNode* front; // 队头指针 QueueNode* rear; // 队尾指针 } LinkedQueue;入队操作 O(1)- 为什么是常数时间通过ai解决int enqueueLinked(LinkedQueue* q, int value) { // 1. 创建新节点 O(1) QueueNode* newNode (QueueNode*)malloc(sizeof(QueueNode)); // 2. 设置数据 O(1) newNode-data value; newNode-next NULL; if (isEmptyLinkedQueue(q)) { // 3. 直接设置 front 和 rear O(1) q-front q-rear newNode; } else { // 4. 直接插入到队尾 O(1) q-rear-next newNode; // 通过 rear 直接访问尾部 q-rear newNode; // 更新 rear } return 1; // 总共4个O(1)操作 O(1) }关键点通过rear 指针所以不需要遍历就能直接找到尾部出队操作 O(1)- 单链表需要从头遍历吗int dequeueLinked(LinkedQueue* q, int* value) { // 1. 检查空队列 O(1) if (isEmptyLinkedQueue(q)) return 0; // 2. 直接从 front 获取数据 O(1) QueueNode* temp q-front; *value temp-data; // 3. 移动 front 指针 O(1) q-front q-front-next; // 4. 特殊情况处理 O(1) if (q-front NULL) { q-rear NULL; } // 5. 释放内存 O(1) free(temp); return 1; // 总共5个O(1)操作 O(1) }不需要有front 指针直接指向头部删除就是移动这个指针。2.循环队列时间复杂度#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; // 连续内存空间 int front; // 队头索引 int rear; // 队尾索引 } CircularQueue;所有操作 O(1)- 数组随机访问特性// 入队 O(1) int enqueueCircular(CircularQueue* q, int value) { if (isFullCircularQueue(q)) return 0; // O(1) - 简单比较 // 数组的随机访问是 O(1) q-data[q-rear] value; // O(1) - 直接下标访问 q-rear (q-rear 1) % MAX_SIZE; // O(1) - 简单计算 return 1; // 总3个O(1)操作 O(1) } // 出队 O(1) int dequeueCircular(CircularQueue* q, int* value) { if (isEmptyCircularQueue(q)) return 0; // O(1) *value q-data[q-front]; // O(1) - 直接下标访问 q-front (q-front 1) % MAX_SIZE; // O(1) - 简单计算 return 1; // 总3个O(1)操作 O(1) }关键点数组通过下标访问任意位置都是 O(1)这是由内存的物理特性决定的地址 基地址 下标 × 元素大小一次计算就能定位不需要遍历二、空间复杂度分析1.链队列的空间复杂度// 每个节点需要 struct QueueNode { int data; // 4字节假设int是4字节 struct QueueNode* next; // 8字节64位系统 // malloc 还有额外的头部开销通常8-16字节 }; // 空间计算 // 有效数据4字节 // 指针开销8字节 // 内存对齐和malloc开销约12字节 // 总共约24字节存储一个int // 如果有n个元素 // 空间复杂度 O(n) // 但实际上空间利用率 ≈ 4/24 ≈ 16.7%2.循环队列的空间复杂度// 固定分配 #define MAX_SIZE 100 // 预分配100个int的位置 int data[MAX_SIZE]; // 400字节4×100 // 空间计算 // 有效数据4×n字节 // 额外空间两个int指针8字节 // 总共400 8 408字节 // 空间复杂度 O(n) 但n是固定的 // 空间利用率最高可达 (MAX_SIZE-1)/MAX_SIZE ≈ 99% // 注意循环队列通常牺牲一个空间区分空和满 // 实际内存布局 // [front][rear][data[0]][data[1]]...[data[99]]三、复杂度对比表格操作链队列循环队列原因分析入队O(1)O(1)都有尾指针/尾索引直接访问出队O(1)O(1)都有头指针/头索引直接访问查找O(n)O(1)数组支持随机访问链表需要遍历空间O(n)O(n)但实际开销不同内存开销高~24字节/元素低4字节/元素链表有指针和malloc开销缓存友好度差节点不连续好连续内存数组能利用CPU缓存预取内存碎片可能产生无链表频繁malloc/free