用C语言举例讲解数据结构中的算法复杂度结与顺序表
更新时间:2020年4月25日 17:36 点击:1262
数据结构算法复杂度
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)个数据元素的有限序列,即:
- 线性表(List)是零个或多个数据元素的集合
- 线性表中的数据元素之间是有顺序的
- 线性表中的数据元素个数是有限的
- 线性表中的数据元素的类型必须相同
//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; }
上一篇: C/C++仿华容道小游戏
下一篇: C语言打印杨辉三角示例汇总
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25