算法概述

  • 原创
  • Madman
  • /
  • /
  • 0
  • 1473 次阅读

Synopsis: 算法是设计良好的可计算的过程,它把某个值或某些值作为输入并产生某个值或某些值作为输出。通常设计一个解决问题的算法是很容易的,但如果这个算法很慢,就要重新设计了。因为算法运行的速度取决于它运行的环境以及实现的细节,计算机科学家们倾向于把运行时间以输入的大小来表示,比如O(n)

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

1. 特征

An algorithm is a sequence of unambiguous instructions used for solving a problem, which can be implemented (as a program) on a computer

算法是解决问题的方法,可以用不同的计算机语言去实现该算法,重要的是算法的思想!

algorithm

算法的五个特征如下:

  • 输入(Input): 一个算法必须有0个或0个以上输入量。Every algorithm must take zero or more number of input values from external.
  • 输出(Output): 一个算法应有1个或1个以上输出量,输出量是算法计算的结果。Every algorithm must produce an output as result.
  • 明确性(Definiteness): 算法的描述必须无歧义,算法中的每个语句/指令都必须清晰明确(只有一种解释)。Every statement/instruction in an algorithm must be clear and unambiguous (only one interpretation)
  • 有限性(Finiteness): 算法必须在有限个步骤内完成任务。For all different cases, the algorithm must produce result within a finite number of steps.
  • 有效性(Effectiveness): 又称可行性,算法中描述的每个操作,都可以通过执行有限次的基本运算来实现。Every instruction must be basic enough to be carried out and it also must be feasible.

2. 算法的性能

一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。Performance analysis of an algorithm is the process of calculating space required by that algorithm and time required by that algorithm.

2.1 时间复杂度

算法的时间复杂度(Time Complexity)是指算法需要消耗的时间。一般来说,计算机算法是问题规模 n 的函数 f(n),算法执行时间的增长率与 f(n) 的增长率正相关,称作渐近时间复杂度,简称时间复杂度

时间复杂度常用大O符号(Big Oh)表述,不包括这个函数的低阶项和首项系数,算法的时间复杂度也因此记做:T(n) = O(f(n))

常见的时间复杂度有:

  • O(1): 常数阶(不会随 n 的大小而改变)
  • O(log n): 对数阶
  • O(n): 线性阶
  • O(n log n): 线性对数阶
  • O(n²): 平方阶
  • O(n³): 立方阶
  • O(2^n): 指数阶
  • O(n!): 阶乘阶

随着问题规模 n 的不断增大,上述时间复杂度不断增大,算法的执行效率越低

时间复杂度

注意: 主要关注算法的最坏时间复杂度

2.2 空间复杂度

算法完成其执行所需的计算机内存总量称为该算法的空间复杂度(Space Complexity),它的计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示,记做:S(n) = O(f(n))

通常,当程序运行时,需要计算机内存用于以下情况:

  1. Instruction Space: It is the amount of memory used to store compiled version of instructions.
  2. Environmental Stack: It is the amount of memory used to store information of partially executed functions at the time of function call.
  3. Data Space: It is the amount of memory used to store all the variables and constants.

时间复杂度相比,空间复杂度的分析要简单得多,我们只考虑数据空间(Data Space)并忽略指令空间以及环境堆栈,这意味着我们只计算存储变量常量结构等所需的内存

2.3 示例

问题: 如果a + b + c = 1000,且a^2 + b^2 = c^2(a,b,c 为自然数),如何求出a、b、c的所有可能组合?

首先创建一个timethis.py模块文件,用来统计每个算法函数耗费的时间:

import time
from functools import wraps


def timethis(func):  # 装饰器,输出被装饰的函数的运行时间
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = time.process_time()
        r = func(*args, **kwargs)
        
                                
                            
  • ymfeelcn
  • Joher
  • kevingaoyong
  • 0x0916
  • shit
  • Peter-haotian-cui
  • stevenszhou20
  • picawen
  • 十一
  • 高压锅嚼起来咯牙
  • 794754074
  • haoyu36
未经允许不得转载: LIFE & SHARE - 王颜公子 » 算法概述

分享

作者

作者头像

Madman

如需 Linux / Python 相关问题付费解答,请按如下方式联系我

0 条评论

暂时还没有评论.