当前位置：首页 > news >正文

复杂度和顺序表（双指针方法）

news 2025/5/1 6:47:40

前言：

时间复杂度和空间复杂度是用于判断算法好坏的指标，程序性能的核心指标。时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。

一、时间复杂度和空间复杂度

1.1概念

时间复杂度：算法的时间复杂度是⼀个函数式T(N)。T(N)=执行次数，而时间复杂度就是表示执行次数的增长量。而我们复杂度的表⽰通常使⽤⼤O的渐进表⽰法。递归算法时间度=单次递归的时间复杂度*递归次数（这里递归过程中函数创建是没有执行次数的，只有计算过程才会执行，我们算的就是计算次数也就是执行次数。而我们可以用递归次数来等效替换执行次数，因为递归了多少次，那就要算多少次）

空间复杂度：空间复杂度指的是该算法所需要开辟的空间（这里开辟的空间指的是需要的算法开辟空间，而外部函数不算里面）。

以上是复杂度函数图。 $\log _{2}^{}\textrm{n}$ 或者其他在复杂度图中都是以logn或者lg表示。

1.2规则

1.在T(N)表示式中，T(N)= $N^{2}$ +N+1，时间复杂度只会取最具有影响的参数，这里保留最高阶项，在这里最高是 $N^{2}$ ，所以复杂度为O( $N^{2}$ )。

2.如果最高阶项数不是1，以1来算，因为到后面最高阶项数对最高阶项影响越来越小了。如T(N)= $\frac{1}{2}$ $N^{2}$ +N+1,最终时间复杂度为O( $N^{2}$ )。

3.如果在T(N)表示式中只有常数，T(N)=1000，那么统一时间复杂度为O(1)。注意：这里无论是多少万甚至多少亿，统一时间复杂度都为O(1)，这里时间复杂度就是表示增长量，而不是数量多少。

4.对于不确定的因素统一以最高来算，这里不确定因素主要是不确定T(N)表达式的确定值，可能受到外界变量影响（受元素大小影响，如排序这些），可能T(N)= $\frac{1}{2}$ $N^{2}$ 也可能为 $\frac{_{1}}{4}$ $N^{2}$ ，也可能为 $N^{2}$ ，还有可能为N，那就以最高来算也就是时间复杂度为O( $N^{2}$ )。

空间复杂度和时间复杂度规则一模一样，因为都是根据一个函数来计算的，函数数据是一样的。

void unc(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}

这里根据规律得：O(N)= $\log _{2}^{}\textrm{n}$ 。

二、顺序表

2.1静态顺序表

顺序表底层原理就是数组，因此物理结构上和逻辑结构上都是线性的。，静态数组是有确定的空间，不能改变空间。

2.2动态顺序表

而动态顺序表，可以扩容空间，可以根据需求，扩容空间以达到想要的效果。

接下来可以根据我们对于动态顺序表进行初始化：

//初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}

扩容：

//扩容空间
void SLCheckCapacity(SL* ps)
{if (ps->capacity == ps->size)//扩容条件{int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//防止空间为0，用三目操作符来扩容加判断SLDateType* tmp = realloc(ps->arr, newcapacity * sizeof(SLDateType));//扩容if (tmp == NULL){perror("realloc");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}
}

尾插：

//尾插
void SLPushBack(SL* ps, SLDateType x)
{assert(ps);//防空//空间不够SLCheckCapacity(ps);//空间够ps->arr[ps->size++] = x;
}

头插：

//头插
void SLPushFront(SL* ps, SLDateType x)
{assert(ps);//空间不够SLCheckCapacity(ps);//空间够for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}

任意插：

//任意插
void SLInsert(SL* ps, int pos, SLDateType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//空间不够SLCheckCapacity(ps);//空间够for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}

尾删：

//尾删
void SLPopBack(SL* ps)
{assert(ps);ps->size--;
}

头删：

//头删
void SLPopFront(SL* ps)
{assert(ps&& ps->size != 0);for (int i = 0; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

任意删：

//任意删
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

三、双指针法

一般遇到算法题，我们会选择暴力解题，这是最简单的方法，而对于有时间复杂度要求的题目我们也可以使用用空间换时间（创建新数组来换），而有一种方法是既可以将时间复杂度降下来，也不用使用空间换时间。这种方法就是双指针法。

用一道题来举例:26. 删除有序数组中的重复项 - 力扣（LeetCode）

int removeDuplicates(int* nums, int numsSize) {int dest = 0; int src = dest + 1;while (src != numsSize){if(nums[dest]!=nums[src]&&++dest != src)//既能++，也能避免重复交换根据&&短路{nums[dest] = nums[src];}src++;}return dest+1;
}

这个双指针，可以用于需要对比，并且还需要筛选不同的数据。该方法能够用2个变量来降低复杂度。

四、总结

顺序表在这样的结构中，可以便捷地在数组上执行数据的增加、删除、查找以及修改等操作。通过这种连续存储的特性，顺序表能够高效地访问元素，尤其是在已知索引的情况下，可以迅速获取对应位置的数据。

复杂度是评判算法好坏的指标

双指针法、空间换时间和暴力，双指针的好处，用于数据对比加数据保留，一般用于数组内对比并删除数据常见。

查看全文

http://www.xdnf.cn/news/231697.html