算法基础

什么是算法

algorithm,最早来自数学领域的概念

衡量算法好坏的重要标准有两个:

  • 时间复杂度

    我们使用程序执行次数来代表程序运行时间

    1. T(n),程序基本操作执行次数的函数(通过这个函数可以算出来程序执行多少次数),n是问题的规模

    2. 有了T(n),我们是不是就能比较程序运行时间了呢?

      并非如此,确定的函数有诸多不变,我们使用的是渐进时间复杂度,说白了就是简化后的T(n),当n趋向于无穷的时候,次数更高的对结果起决定性的作用,我们就用高次项作为渐进时间复杂度

    3. 渐进时间复杂度:

      如果有f(n),当n趋向于无穷的时候,T(n)/f(n)的值是一个非零的常数,也就是说T(n) f(n)是同等数量级的,记作T(n)=O(f(n)),称为O(f(n)),O为算法的渐进时间复杂度,简称时间复杂度,因为渐进时间复杂度用O表示,所以也被称为大O表示法

    4. 推导时间复杂度的原则

      • 如果运行的时间是常数级,则用常数1来表示

      • 只保留时间函数中的最高阶项

      • 如果最高阶项存在,则省去最高阶项前面的系数

      举例:

      (1)T(n) = 3n

      T(n) = O(n)

      (2)T(n) = 5logn

      T(n) = O(logn)

      (3)T(n) = 5

      T(n) = O(1)

      (4)T(n) = 5n^2

      T(n) = O(n^2)

  • 空间复杂度

    空间复杂度,采用了和时间复杂度类似的大O表示法。表示的是执行算法的空间成本

    在运行一段程序的时候,我们不仅是在执行各种指令,同时也会根据需要,存储临时的中间数据

    1. 空间复杂度的计算

      • 常量空间:算法的存储空间是确定的,不变的,比如就定义了一个变量,空间复杂度记为O(1)

      • 线性空间:分配的空间是一个线性的集合(比如列表),并且集合的大小和输入的规模n成正比,空间复杂度记为O(n)

      • 二维空间:分配的是个二维列表集合,并且长度和宽度都是和n成正比,那就是O(n^2)

      • 递归空间:虽然递归代码中并没有直接显式地声明变量或者集合,但是计算机在执行的时候,会专门分配一块内存,用来存储“函数调用栈“

        每调用一次函数就执行一次入栈操作,把调用的函数和参数信息压入栈中

        递归n次,也就是调用函数n次,栈的深度也就是n

        当函数返回的时候,执行出栈操作,把调用的函数和参数信息从栈中弹出,一一出栈

        执行递归需要的和递归的深度成正比

        也就是说纯粹的递归操作的空间复杂度也是线性的,O(n)

什么是数据结构

数据结构,data structure,数据的组织、管理和存储的格式,其目的是高效地访问和修改数据

  1. 线性结构

    数组,链表、栈、队列、哈希表

  2. 二叉树、二叉堆

  3. 多对多的关联关系

  4. more...

相关推荐