目錄

目錄

目錄

前言：

一、時間復雜度和空間復雜度

1.1概念

1.2規則

二、順序表

2.1靜態順序表

2.2動態順序表

三、雙指針法

四、總結

---

前言：

????????時間復雜度和空間復雜度是用于判斷算法好壞的指標，程序性能的核心指標。時間復雜度主要衡量?個算法的運?快慢，?空間復雜度主要衡量?個算法運?所需要的額外空間。

一、時間復雜度和空間復雜度

1.1概念

? ? ? ? 時間復雜度：算法的時間復雜度是?個函數式T(N)。T(N)=執行次數，而時間復雜度就是表示執行次數的增長量。而我們復雜度的表?通常使??O的漸進表?法。遞歸算法時間度=單次遞歸的時間復雜度*遞歸次數（這里遞歸過程中函數創建是沒有執行次數的，只有計算過程才會執行，我們算的就是計算次數也就是執行次數。而我們可以用遞歸次數來等效替換執行次數，因為遞歸了多少次，那就要算多少次）

? ? ? ? 空間復雜度：空間復雜度指的是該算法所需要開辟的空間（這里開辟的空間指的是需要的算法開辟空間，而外部函數不算里面）。

以上是復雜度函數圖。?或者其他在復雜度圖中都是以logn或者lg表示。

1.2規則

? ? ? ? 1.在T(N)表示式中，T(N)=+N+1，時間復雜度只會取最具有影響的參數，這里保留最高階項，在這里最高是，所以復雜度為O()。

? ? ? ? 2.如果最高階項數不是1，以1來算，因為到后面最高階項數對最高階項影響越來越小了。如T(N)=+N+1,最終時間復雜度為O()。

? ? ? ? 3.如果在T(N)表示式中只有常數，T(N)=1000，那么統一時間復雜度為O(1)。注意：這里無論是多少萬甚至多少億，統一時間復雜度都為O(1)，這里時間復雜度就是表示增長量，而不是數量多少。

? ? ? ? 4.對于不確定的因素統一以最高來算，這里不確定因素主要是不確定T(N)表達式的確定值，可能受到外界變量影響（受元素大小影響，如排序這些），可能T(N)=也可能為，也可能為，還有可能為N，那就以最高來算也就是時間復雜度為O()。

空間復雜度和時間復雜度規則一模一樣，因為都是根據一個函數來計算的，函數數據是一樣的。

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

?這里根據規律得：O(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個變量來降低復雜度。

四、總結

順序表在這樣的結構中，可以便捷地在數組上執行數據的增加、刪除、查找以及修改等操作。通過這種連續存儲的特性，順序表能夠高效地訪問元素，尤其是在已知索引的情況下，可以迅速獲取對應位置的數據。

?復雜度是評判算法好壞的指標

雙指針法、空間換時間和暴力，雙指針的好處，用于數據對比加數據保留，一般用于數組內對比并刪除數據常見。