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

复杂度扫尾+链表经典算法题

backend 2025/8/26 17:45:35

1.复杂度扫尾

1.1 计算阶乘递归Fac的时间复杂度

//计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if(0 ==N)return 1;return Fac(N-1)*N;
}

时间复杂度是O(N)。

函数Fac接受一个参数N，用于计算N的阶乘。

当N等于0时，返回1（因为0的阶乘定义为1）。否则返回Fac(N-1)*N,即通过调用Fac(N-1)来计算（N-1)的阶乘，再乘以N到N的阶乘。

时间复杂度主要看递归调用的次数。

计算Fac(N)时，需要调用Fac(N-1)，计算Fac(N-1)时，需要调用Fac(N-2);此次类推，直到调用Fac(0)时返回1，递归结束，这样的递归调用次数就是N次（从N到0，共N+1次调用，但在时间复杂度的大O表示中，常数项可以省略，所以近似为N次）。

1.1.1 计算阶乘递归Fac的时间复杂度对比

//计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if(0 ==N)return 1;for(int i=0;i<N;++i){//...}return Fac(N-1)*N;
}

除了递归调用的次数之外，跟1.1是一样的逻辑，这个代码除了终止条件Fac(0)，都有一个for循环，当计算Fac(N)时，for循环执行N次，计算Fac(N-1)时，for循环执行N-1次，计算Fac(1)时，for循环执行1次，当Fac(0)无循环，直接返回1.

总操作次数就是各层递归中for循环执行次数的总和，即N+(N-1)+(N-2)+...+1，这是一个等差数列求和，首项1加尾项N的和乘以项数N，最后总时间复杂度为O(N^2)。

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

//计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if(N<3)return 1;return Fib(N-1)+Fib(N-2);
}

1.3 计算BubbleSort的时间复杂度

// 计算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;}
}

函数栈帧在编译期间已经确定好了，只需要关注函数在运行时额外申请的空间。
BubbleSort额外申请的空间有exchange等有限个局部变量，使用了常数个额外空间
因此空间复杂度为 O(1)

2. 链表经典算法题

2.1 返回倒数第k个节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {ListNode* fast=head,*slow=head;//快指针先走k步while(k--){fast=fast->next;//快指针先向后移动k次，每次移动都向后移动一位，这样快慢指针相差k个节点}//同时走while(fast){slow=slow->next;fast=fast->next;//最开始快指针领先慢指针k步，当fast走到链表末尾时，slow刚好指向了倒数第k个节点}return slow->val;//返回slow节点的val值
}

2.2 链表的回文结构

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:struct ListNode* middleNode(struct ListNode* head)//寻找链表中间节点{struct ListNode* slow=head,* fast=head;while(fast&& fast->next){slow=slow->next;fast=fast->next->next;}return slow;}struct ListNode* reverseList(struct ListNode* head)//转置链表{struct ListNode* pcur=head;//定义一个pcur遍历链表struct ListNode* newhead=NULL;//创建一个新的链表while(pcur){struct ListNode* next=pcur->next;//头插pcur->next=newhead;newhead=pcur;pcur=next;}return newhead;}bool chkPalindrome(ListNode* A) {struct ListNode* mid=middleNode(A);struct ListNode* rmid=reverseList(mid);while(rmid && A){if(rmid->val!=A->val){return false;}rmid=rmid->next;A=A->next;}return true; //对应的函数要有返回值}
};

单链表专题---暴力算法美学(1)(有视频演示）-CSDN博客，寻找链表的中间节点详解

2.3 相交链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//先用两个指针遍历链表struct ListNode* curA=headA,*curB=headB;int lenA=1,lenB=1;//这里一定要定义lenA和lenB的初始化长度为1，否则下面longList会有变成空指针的可能while(curA){curA=curA->next;lenA++;}while(curB){curB=curB->next;lenB++;}//尾节点不相等就不相交if(curA != curB){return NULL;}//长的先走差距步，再同时走，第一个相等的就是交点//这里用假设法int gap=abs(lenA-lenB);//abs就是求绝对值struct ListNode* longList=headA,* shortList=headB;if(lenB>lenA){longList=headB;shortList=headA;}while(gap--){longList=longList->next;//长链表先走差距步}while(longList!=shortList)//跳出循环的条件就是longList=shortList{longList=longList->next;shortList=shortList->next;}return shortList;//相交的节点,这里也可以写longList，因为此时两个指针指向的是同一个位置
}

查看全文

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