數據結構算法復雜度
1、影響算法效率的主要因素
（1）算法采用的策略和方法；
（2）問題的輸入規模；
（3）編譯器所產生的代碼；
（4）計算機執行速度。
2、時間復雜度
// 時間復雜度：2n + 5 long sum1(int n) { long ret = 0; //1 int* array = (int*)malloc(n * sizeof(int)); //1 int i = 0; //1 for(i=0; i<n; i++) //n { array[i] = i + 1; } for(i=0; i<n; i++) //n { ret += array[i]; } free(array); //1 return ret; //1 } //時間復雜度: n + 3 long sum2(int n) { long ret = 0; //1 int i = 0; //1 for(i=1; i<=n; i++) //n { ret += i; } return ret; //1 } //時間復雜度: 3 long sum3(int n) { long ret = 0; //1 if( n > 0 ) { ret = (1 + n) * n / 2; //1 } return ret; //1 } 隨著問題規模n的增大，它們操作數量的差異會越來越大，因此實際算法在時間效率上的差異也會變得非常明顯！
判斷一個算法的效率時，往往只需要關注操作數量的最高次項，其它次要項和常數項可以忽略。
在沒有特殊說明時，我們所分析的算法的時間復雜度都是指最壞時間復雜度。
3、空間復雜度
//空間復雜度：12 + n long sum1(int n) { long ret = 0; //4 int* array = (int*)malloc(n * sizeof(int)); //4 + 4 * n int i = 0; //4 for(i=0; i<n; i++) { array[i] = i + 1; } for(i=0; i<n; i++) { ret += array[i]; } free(array); return ret; } //空間復雜度: 8 long sum2(int n) { long ret = 0; //4 int i = 0; //4 for(i=1; i<=n; i++) { ret += i; } return ret; } //空間復雜度: 4 long sum3(int n) { long ret = 0; //4 if( n > 0 ) { ret = (1 + n) * n / 2; } return ret; } 多數情況下，算法執行時所用的時間更令人關注,如果有必要，可以通過增加空間復雜度來降低時間復雜度,同理，也可以通過增加時間復雜度來降低空間復雜度，具體問題，具體分析。
數據結構順序表
表是具有相同類型的n（n >= 0）個數據元素的有限序列,即：
//seq_list.h #ifndef _SEQ_LIST_H_ #define _SEQ_LIST_H_ struct seq_list { int capacity; int length; unsigned int *node; }; struct seq_list* seq_list_create(int capacity); int seq_list_capacity(struct seq_list* list); int seq_list_length(struct seq_list* list); int seq_list_insert(struct seq_list* list, int position, void* data); void* seq_list_get(struct seq_list* list, int position); void* seq_list_remove(struct seq_list* list, int position); void seq_list_clear(); void seq_list_destroy(struct seq_list* list); #endif //seq_list.c #include "seq_list.h" #include <stddef.h> #include <malloc.h> struct seq_list* seq_list_create(int capacity) { int i = 0; struct seq_list* ret = NULL; if (capacity >= 0) { ret = (struct seq_list*) malloc(sizeof(struct seq_list) + sizeof(unsigned int) * capacity); if (ret != NULL) { ret->capacity = capacity; ret->length = 0; ret->node = (unsigned int*) (ret + 1); } } return ret; } int seq_list_insert(struct seq_list* list, int position, void* data) { int i = 0; int ret; ret = (list != NULL); ret = ret && position >= 0 && position < list->capacity; ret = ret && list->length < list->capacity; if (ret) { for (i = list->length; i > position; i--) { list->node[i] = (list->node[i - 1]); } list->node[i] = (unsigned int)data; double *p = (double *)data; list->length++; } return ret; } void* seq_list_get(struct seq_list* list, int position) { void* ret = NULL; if (list != NULL && position >= 0 && position < list->length) { ret = (void *)list->node[position]; } return ret; } void* seq_list_remove(struct seq_list* list, int position) { void* ret = NULL; int i = 0; if (list != NULL && position >= 0 && position < list->length) { int i = 0; ret = seq_list_get(list, position); for (i = position + 1; i < list->length; i++) { list->node[i - 1] = list->node[i]; } list->length--; } return ret; } int seq_list_capacity(struct seq_list* list) { int ret = -1; if (list != NULL) { ret = list->capacity; } return ret; } int seq_list_length(struct seq_list* list) { int ret = -1; if (list != NULL) { ret = list->length; } return ret; } void seq_list_clear(struct seq_list* list) { if (list != NULL) { list->length = 0; } } void seq_list_destroy(struct seq_list* list) { free(list); list = NULL; } //seq_list_main.c #include <stdio.h> #include "seq_list.h" int main(void) { struct seq_list* list = seq_list_create(100); double *p = NULL; int ret = 0; double a = 1.1; double b = 2.2; double c = 3.3; double d = 4.4; double e = 5.5; seq_list_insert(list, 0, &a); seq_list_insert(list, 1, &b); seq_list_insert(list, 2, &c); seq_list_insert(list, 3, &d); seq_list_insert(list, 4, &e); printf("list capacity = %d, length = %d/n", seq_list_capacity(list), seq_list_length(list)); p = (double *)seq_list_get(list, 0); if (p != NULL) { printf("%lf/n", *p); } p = (double *)seq_list_get(list, 3); if (p != NULL) { printf("%lf/n", *p); } p = (double *)seq_list_remove(list, 3); if (p != NULL) { printf("remove data %lf, index at 3 , after length: %d/n", *p, seq_list_length(list)); } p = (double *)seq_list_get(list, 3); if (p != NULL) { printf("after remove, index at 3: %lf/n", *p); } seq_list_clear(list); printf("after clear, list length is %d/n", seq_list_length(list)); seq_list_destroy(list); return 0; } 新聞熱點
疑難解答
圖片精選
