用C語言舉例講解數(shù)據(jù)結(jié)構(gòu)中的算法復(fù)雜度結(jié)與順序表

更新時間：2016年02月24日 14:38:40 作者：喝醉的毛毛蟲

這篇文章主要介紹了講解數(shù)據(jù)結(jié)構(gòu)中的算法復(fù)雜度結(jié)與順序表的C語言版示例,包括對時間復(fù)雜度和空間復(fù)雜度等概念的簡單講解,需要的朋友可以參考下

數(shù)據(jù)結(jié)構(gòu)算法復(fù)雜度
1、影響算法效率的主要因素
（1）算法采用的策略和方法；

（2）問題的輸入規(guī)模；

（3）編譯器所產(chǎn)生的代碼；

（4）計算機執(zhí)行速度。

2、時間復(fù)雜度

// 時間復(fù)雜度：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 
} 
 
 
\\時間復(fù)雜度: 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 
} 
 
\\時間復(fù)雜度: 3 
long sum3(int n) 
{ 
  long ret = 0; \\1 
   
  if( n > 0 ) 
  { 
    ret = (1 + n) * n / 2; \\1 
  } 
   
  return ret; \\1 
}

隨著問題規(guī)模n的增大，它們操作數(shù)量的差異會越來越大，因此實際算法在時間效率上的差異也會變得非常明顯！

2016224143347658.png (722×422)

判斷一個算法的效率時，往往只需要關(guān)注操作數(shù)量的最高次項，其它次要項和常數(shù)項可以忽略。

2016224143415099.jpg (675×348)

在沒有特殊說明時，我們所分析的算法的時間復(fù)雜度都是指最壞時間復(fù)雜度。

2016224143440710.jpg (669×394)

3、空間復(fù)雜度

//空間復(fù)雜度：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; 
} 
 
 
\\空間復(fù)雜度: 8 
long sum2(int n) 
{ 
  long ret = 0; \\4 
  int i = 0; \\4 
   
  for(i=1; i<=n; i++) 
  { 
    ret += i; 
  } 
   
  return ret; 
} 
 
\\空間復(fù)雜度: 4 
long sum3(int n) 
{ 
  long ret = 0; \\4 
   
  if( n > 0 ) 
  { 
    ret = (1 + n) * n / 2; 
  } 
   
  return ret; 
}

多數(shù)情況下，算法執(zhí)行時所用的時間更令人關(guān)注,如果有必要，可以通過增加空間復(fù)雜度來降低時間復(fù)雜度,同理，也可以通過增加時間復(fù)雜度來降低空間復(fù)雜度，具體問題，具體分析。

數(shù)據(jù)結(jié)構(gòu)順序表
表是具有相同類型的n（n >= 0）個數(shù)據(jù)元素的有限序列,即：

線性表(List)是零個或多個數(shù)據(jù)元素的集合
線性表中的數(shù)據(jù)元素之間是有順序的
線性表中的數(shù)據(jù)元素個數(shù)是有限的
線性表中的數(shù)據(jù)元素的類型必須相同

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

您可能感興趣的文章: