对于包含n个元素的一维数组,创建一个有序单链表的算法,时间复杂度

2025-03-11 09:18:01
推荐回答(2个)
回答1:

在一个具有n个节点的单链表中删除第i个节点算法的时间复杂度是O(n);因最坏情况是删除最后一个结点,所以要找到最一个结点的前驱,也就要访问前n-1个结点,故算法的时间复杂度为O(n);

回答2:

n(n-1)/2
第一个数,0次查找
第二个数,1次查找
...
第n个数,n-1次查找
所以总共为:
(n-1+1)(n-1)/2=n(n-1)/2
上面含有平方介,所以他的时间复杂度为n^2