算法特性和算法复杂度

程序=数据结构+算法。

算法：

算法就是解特定问题的方法，是对特定问题求解步骤的一种描述。算法是计算机学科中最具方法论性质的核心概念，是计算机科学的灵魂。

算法特性：5个特性

1.有穷性。必须执行有究步有限的时间内可以结束，不能一直执行下去。不然就成了无穷性就没有实际意义。

2.确定性。每一步都有要确切的含义，对相同输入要有相同的输出。

3.可行性。也就是说通过执行基本操作有限次可以实现。

4.算法有零个或多个输入。要有处理对象，也可以说是数据。可以通过嵌入到算法中（零个输入），或通过赋值方法使变量获得数据（一个或多个输入）。

5.算法有零个或多个输出。一个算法一定要有输出，也就是执行结果。可以返回数据，或是执行某个行为。

算法时间复杂度：

算法的时间复杂度是评估算法的重要标准之一，它能较了地体现算法本身的时间效率，而与具体实现算法的计算机软件、硬件无关。

分析一个算法的进间复杂度首先要从中选取一种能在很大程度上体现该算法执行时间的基本操作，以该基本操作重复执行的次数作为度量。

一般情况下，算法基本操作重复执行的次数是问题规模n的某个函数f(n)。而算法的时间复杂度简单来说是指算法中某种基本操作执行次数的数量级。通常用T(n)=O(f(n))表示，其中O表示f(n)的数量级

例如：在矩阵相乘的算法中，乘法就是基本操作。

问题规模为n，基本操作乘法的执行次数f(n) ≈n*n*n，所以T(n)=O(n3)。

算法空间复杂度：

与算法时间复杂度类似，算法空间复杂度作为算法所需存储空间的量度，记作：

S(n)=O(f(n))

n是问题的规模，算法所需的存储空间是问题规模n的函数f(n)。算法空间复杂度也重要，但相对于时间复杂度来讲并没哪么重要（因为现在电脑内存都比较大）但在设计算法时“时、空”都要考虑进去，尽量避免存储空间的浪费。

 

相关文章:

  1. 最大子列和问题
    给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11,...
  2. 二分查找算法
    本题要求实现二分查找算法。函数接口定义：Position BinarySearch( List L, ElementType X );其中List结构定义如下：typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last;...
  3. 如何获取一段代码运行时间
    C++语言如何获取一段代码运行时间，可以使用clock()函数来完成，定义在time.h头文件中。 clock()是C/C++中的计时函数，而与其相关的数据类型是clock_t。 定义：clock_t clock(void) ;...
  4. 标准c时间与日期函数
    asctime() 时间文本格式 clock() 返回自程序开始运行所经过的时间 ctime() 返回特定格式时间 difftime() 两时刻的间隔 gmtime() 返回指向当前格林威治时间的指针 localtime() 返回指向当前时间的指针...
  5. clock()函数clock
    clock()函数clock 语法: #include clock_t clock( void ); 功能：函数返回自程序开始运行的处理器时间，如果无可用信息，返回-1。 转换返回值以秒记, 返回值除以CLOCKS_PER_SECOND. (注: 如果编译器是POSIX兼容的, CLOCKS_PER_SECOND定义为1000000.)...
  6. ctime()函数ctime
    ctime()函数ctime 语法: #include char *ctime( const time_t *time ); 功能：函数转换参数time为本地时间格式： ctime功能是 把日期和时间转换为字符串，...
  7. difftime()函数difftime
    difftime()函数difftime 语法: #include double difftime( time_t time2, time_t time1 ); 功能：函数返回时间参数time2和time1之差的秒数表示。...
  8. gmtime()函数gmtime
    gmtime()函数gmtime 语法: #include struct tm *gmtime( const time_t *time ); 功能：函数返回给定的统一世界时间（通常是格林威治时间），如果系统不支持统一世界时间系统返回NULL。 警告!...
  9. 画八段管显示时间动态更新
    1.设计一个类Eightpipe，用于实现单个八段管里面的8条线位置，还有0-9数字如何显示定义。类里面定义一个数组变量 TShape* Pipe[7]，用于显示8条线。2.在主程式中定义6个Eightpipe对象( EightPipe* Pipe[6])，时2个，分2个，秒两个3.获取时间，跟据时、分、秒来分别设置显示，每秒更新一次...
  10. 数据结构概念和分类
    数据结构（data structure)数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据元素间的关系称为结构。客观事物之间存在着各种不同的联系，但将其抽象为数据以后再来研究它们所具有的共性关系就简单得多。...

《算法特性和算法复杂度》上有22条评论

评论已关闭。