❶ 為什麼在單鏈表中,從頭開始遍歷,訪問後繼節點的時間復雜度為o(1)，訪問前驅節點的時間復雜度為o
訪問後繼結點只要一次間接定址p = p->next，該步驟沒有循環，時間復雜度是O(1)
訪問前驅節點需要從頭結點開始根據鏈表順序一個一個訪問。該步驟有一重循環，基本運算次數與問題規模n的增長呈線性增大關系，所以時間復雜度是O(n)。
如果是雙向鏈表p = p->prior就能訪問前驅節點。
❷ 將長度為n的單鏈表鏈接在長度為m的單鏈表之後的演算法的時間復雜度為
要插入到長度為m的單鏈表，需要找到表尾，這個過程的時間復雜度為o(m)，連接的時間復雜度為o(1)，所以總的時間復雜度為o(m)，所以答案選C。
單鏈表是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。鏈表中的數據是以結點來表示的，每個結點的構成：元素(數據元素的映象) +指針(指示後繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。
時間復雜度是同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。
時間復雜度的計算方法：
1、一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n)，使得T(n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))，稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。
分析：隨著模塊n的增大，演算法執行的時間的增長率和 f(n) 的增長率成正比，所以 f(n) 越小，演算法的時間復雜度越低，演算法的效率越高。
2、在計算時間復雜度的時候，先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出 T(n) 的同數量級，找出後，f(n) = 該數量級，若 T(n)/f(n) 求極限可得到一常數c，則時間復雜度T(n) = O(f(n))。
(2)單鏈表訪問後繼節點復雜度擴展閱讀
單鏈表的建立有頭插法、尾插法兩種方法。
1、頭插法：
單鏈表是用戶不斷申請存儲單元和改變鏈接關系而得到的一種特殊數據結構，將鏈表的左邊稱為鏈頭，右邊稱為鏈尾。頭插法建單鏈表是將鏈表右端看成固定的，鏈表不斷向左延伸而得到的。頭插法最先得到的是尾結點。
由於鏈表的長度是隨機的，故用一個while循環來控制鏈表中結點個數。假設每個結點的值都大於O，則循環條件為輸入的值大於o。
申請存儲空間可使用malloc()函數實現，需設立一申請單元指針，但malloc()函數得到的指針並不是指向結構體的指針，需使用強制類型轉換，將其轉換成結構體型指針。剛開始時，鏈表還沒建立，是一空鏈表，head指針為NULL。
鏈表建立的過程是申請空間、得到數據、建立鏈接的循環處理過程。
2、尾插法：
若將鏈表的左端固定，鏈表不斷向右延伸，這種建立鏈表的方法稱為尾插法。尾插法建立鏈表時，頭指針固定不動，故必須設立一個搜索指針，向鏈表右邊延伸，則整個演算法中應設立三個鏈表指針，即頭指針head、搜索指針p2、申請單元指針pl。尾插法最先得到的是頭結點。
❸ 建立一個有n個元素的有序單鏈表的時間復雜度度為什麼是O(n^2) 求詳解哇……(>﹏<)
因為o（n^2），對單鏈表而言，一些快速的排序演算法，不能用，只能用直接插入等o（n^2）級的排序演算法來實現排序。因為是有序單鏈表那麼每次插入到鏈表尾結點，那麼每次插入都要從頭掃到尾，然後1+2+3+... m = O（m^2）這樣。
鏈表中的數據是以結點來表示的，每個結點的構成：元素(數據元素的映象) +指針(指示後繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。以「結點的序列」表示線性表稱作線性鏈表（單鏈表），單鏈表是鏈式存取的結構。
(3)單鏈表訪問後繼節點復雜度擴展閱讀：
typedef char DataType; //假設結點的數據域類型為字元
typedef struct node{ //結點類型定義
DataType data; //結點的數據域
struct node *next;//結點的指針域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
LinkList head;
注意：
①LinkList和ListNode是不同名字的同一個指針類型。（命名的不同是為了概念上更明確）
②*LinkList類型的指針變數head表示它是單鏈表的頭指針。
③ListNode類型的指針變數p表示它是指向某一結點的指針。
❹ 為什麼單鏈表訪問後繼結點的時間復雜度為O(1),而訪問前驅結點的時間復雜度為O(n)..請詳細的說明原因。謝
訪問後繼結點只是進行一次間接定址的操作，時間是常量，所以是O（1）。
鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其後繼結點的地址（或位置）信息。
單鏈表中可以沒有頭結點，但是不能沒有頭指針！頭節點的引入能使鏈表對第一個元素的刪除和插入和其他元素相同，不用另外說明，使得代碼更加簡潔。
(4)單鏈表訪問後繼節點復雜度擴展閱讀：
獲取需要刪除的節點的上一個節點node，把node的next指向node的next的next，因為node的next節點沒有指針指向它，因此它會被系統自動清理，記錄鏈表長度的變數-1。
public AnyType remove(int i)
{
Node<AnyType> prev=getNode(i-1);
AnyType a=prev.next.data;
prev.next=prev.next.next;
thesize--;
return a;
}
❺ 在單鏈表中刪除一個指定節點的後繼的時間復雜度是多少
時間復雜度是O(n)
在一個具有n個節點的單鏈表中刪除第i個節點演算法的時間復雜度是o(n)；因最壞情況是刪除最後一個結點，所以要找到最一個結點的前驅，也就要訪問前n-1個結點，故演算法的時間復雜度為o(n)。
for（i=1;i<n;i++）;// 由於這里有一個分號，所以執行n次
for(j=1;j<i;j++)// 此時i=n，所以執行n次。
共執行2n次，時間復雜度是O(n)。
(5)單鏈表訪問後繼節點復雜度擴展閱讀：
一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T（n)/f (n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。
在各種不同演算法中，若演算法中語句執行次數為一個常數，則時間復雜度為O(1),另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n2)。
❻ 對於一個具有n個結點的單鏈表，在已知的結點*p後插入一個新結點的時間復雜度為多少為什麼
o(1)，直接定位，時間復雜度為1。
鏈表中的數據是以結點來表示的，每個結點的構成：元素（數據元素的映象） +指針（指示後繼元素存儲位置），元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。
以「結點的序列」表示線性表稱作線性鏈表（單鏈表），單鏈表是鏈式存取的結構。
(6)單鏈表訪問後繼節點復雜度擴展閱讀：
① 用一組任意的存儲單元來存放線性表的結點（這組存儲單元既可以是連續的，也可以是不連續的）
② 鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其後繼結點的地址（或位置）信息（稱為指針（pointer）或鏈(link)）
鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數據結構。
❼ 長度N的單鏈表接在長度M的單鏈表後的演算法時間復雜度是多少 ，要有解釋~
#include<iostream>
#include <malloc.h>
#define FALSE 0
#define TRUE 1
#define OK 1
#define ERROR 0
#define MaxSize 10
using namespace std;
typedef char ElemType;
typedef struct Node
{
ElemType data;
Node *next;
}Node, *LinkList;
int InitList_L(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node));
if(!L)
exit (FALSE);
(*L)->next=NULL;
return TRUE;
}
void qcreate(LinkList L)
{
Node *s;
char c;
int flag=1;
while(flag) /* flag初值為1，當輸入"#"時，置flag為0，建表結束*/
{
c=getchar();
if(c!='#')
{
s=(Node*)malloc(sizeof(Node)); /*建立新結點s*/
s->data=c;
s->next=L->next;/*將s結點插入表頭*/
L->next=s;
}
else
flag=0;
}
}
//計算鏈表長度
void length(LinkList L)
{
Node *p;
p=L->next;
int j=0;
while(p!=NULL)
{
p=p->next;
j++;
}
printf("%d",j);
printf("\n");
}
//輸出鏈表
void printf(LinkList L)
{
LinkList p;
p=L;
while(p->next!=NULL)
{
p=p->next;
printf("%c",p->data);
}
printf("\n");
}
//對鏈表排序
void paixu(LinkList L)
{
Node *r,*q,*small;
char temp;
for(r=L->next;r->next!=NULL;r=r->next)
{
small=r;
for(q=r->next;q;q=q->next) /*找到鏈表中最小字元*/
if(q->data<small->data)
small=q;
if(small!=r)
{
temp=r->data;
r->data=small->data; /*把最小的數值換到P指針所指的位置數值上（原P指針的next指向不變）*/
small->data=temp; /*把原先p指針所指位置的數值填入被置換出的最小字元位置*/
}
}
printf(L);
}
// 查找第i個結點
void Get(LinkList L, int i)
/*在帶頭結點的單鏈表L中查找第i個結點，若找到(1≤i≤n)，則返回該結點的存儲位置; 否則返回NULL*/
{
int j;
Node *p;
p=L;
j=0; /*從頭結點開始掃描*/
while ((p->next!=NULL)&&(j<i))
{
p=p->next; /* 掃描下一結點*/
j++; /* 已掃描結點計數器 */
}
if(i == j)
printf("%c",p->data); /* 找到了第i個結點 */
else
printf("NULL"); /* 找不到，i≤0或i>n */
printf("\n");
}
//在單鏈表中找到與x相同的數值
void Getchar(LinkList &L)
{
char n;
cout<<"輸入這個元素:";
cin>>n;
LinkList p;
p=L;
while(p->data!=n)
{
if(p->next==NULL)
printf("FALSE");
p=p->next;
}
printf("TRUE");
}
// 插入結點
void cins(LinkList L,int i,ElemType x)
/*在帶頭結點的單鏈表L中第i個位置插入值為e的新結點s*/
{
Node *pre,*s;
int k;
pre=L;
k=0; /*從"頭"開始，查找第i-1個結點*/
while(pre!=NULL&&k<i-1) /*表未查完且未查到第i-1個時重復，找到pre指向第i-1個*/
{
pre=pre->next;
k=k+1;
} /*查找第i-1結點*/
if(!pre) /*如當前位置pre為空表已找完還未數到第i個，說明插入位置不合理*/
{
printf("插入位置不合理!");
}
s=(Node*)malloc(sizeof(Node)); /*申請一個新的結點S */
s->data=x; /*值e置入s的數據域*/
s->next=pre->next; /*修改指針，完成插入操作*/
pre->next=s;
printf("插入成功!鏈表為：");
}
//刪除結點
void del(LinkList L,int i)
/*在帶頭結點的單鏈表L中刪除第i個元素，並將刪除的元素保存到變數e中*/
{
Node *pre,*r;
int k;
pre=L;
k=0;
while(pre->next!=NULL && k<i-1) /*尋找被刪除結點i的前驅結點i-1使p指向它*/
{
pre=pre->next;
k=k+1;
} /*查找第i-1個結點*/
if(!(pre->next)) /* 即while循環是因為p->next=NULL或i<1而跳出的,而是因為沒有找到合法的前驅位置，說明刪除位置i不合法。*/
{
printf("刪除結點的位置i不合理!");
}
r=pre->next;
pre->next=pre->next->next; /*修改指針，刪除結點r*/
free(r); /*釋放被刪除的結點所佔的內存空間*/
printf("成功刪除結點!鏈表為:");
}
void main()
{
LinkList L;
InitList_L(&L);
int e,i;
char x;
int flag=1;
printf("初始化單鏈表: (請輸入10個以內的字元,以'#'結尾,之間無須空格)\n");
qcreate(L);
printf(L);
while(flag)
{
printf("請選擇操作:");
printf("\n");
printf("1.插入結點");
printf("\n");
printf("2.刪除結點");
printf("\n");
printf("3.查找第i個元素");
printf("\n");
printf("4.求鏈表長度 ");
printf("\n");
printf("5.是否能在單鏈表中找到與x相同的數值");
printf("\n");
printf("6.輸出鏈表");
printf("\n");
printf("7.排序");
printf("\n");
printf("8.退出");
cin>>e;
switch(e){
case 1:printf("請輸入要插入的元素值:");
cin>>x;
printf("請輸入要在第幾個結點處");
cin>>i;
cins(L,i,x);
printf(L);
break;
case 2: printf("請輸入你要刪除第幾個結點: ");
cin>>i;
del(L,i);
printf(L);
break;
case 3:printf("請輸入位置i: ");
cin>>i;
printf("數值為:");
Get(L,i);
break;
case 4:printf("鏈表長度為:");
length(L);
break;
case 5:Getchar(L);
break;
case 6:printf(L);
break;
case 7:paixu(L);
case 8:flag=0;
break;
}
}
}
請參考
❽ 將長度為n的單鏈表鏈接在長度為m的單鏈表之後的演算法的時間復雜度是多少
要插入到長度為m的單鏈表，需要找到表尾，這個過程的時間復雜度為o(m)，連接的時間復雜度為0(1),所以總的時間復雜度為0(m)