数据结构算法复杂度
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;
}