数据结构与算法基础(准备使用Go来学习)

什么是算法

算法(algorithm),算法在计算机科学中描述为:计算机接受一个输入的指令,然后进行一个过程处理,最后输出计算的结果。
例如:妈妈让打酱油的过程,打酱油的命令是输入,给妈妈酱油是输出
总之,逻辑过程或者行为模式在计算机中的映射是算法
用更准确的描述来说,算法是一种有限,确定,有效的并适合计算机程序来实现的,用来解决问题的方法。
例如:有一个问题,然后有一个方法去解决它,这个方法叫算法

  • 算法是有限的,就是算法的步骤是有限的,执行的时间也是有限的,能够在有限时间内得出结果。

  • 算法也是确定的,就是无论执行多少次计算结果都是一样的

  • 算法是有效的,就是计算出的结果对解决问题有帮助

一个例子:汉诺塔问题描述
在三根杆(编号A,B,C),在A杆自上而下,由大到小按顺序排序放置64个金盘。
游戏目标:把A杆上的金盘全部移到C杆上并保持原有顺序叠好
数据结构与算法基础(准备使用Go来学习)

操作规则:每次只能移动一个盘子,并且在移动的过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A,B,C任意一杆上
我们想到的算法:

  • 借助C杆,将A杆前面N-1个盘子,移动到B杆后,将A杆剩下的一个盘子,直接移动到C杆,只是后A空了
  • 然后借助A杆,将B杆的N-1个盘子,移动到C杆,任务完成
package main

import "fmt"

var total = 0

// 汉诺塔
// 一开始A杆上有N个盘子,B和C杆都没有盘子。
func main() {
    n := 4   // 64 个盘子
    a := "a" // 杆子A
    b := "b" // 杆子B
    c := "c" // 杆子C
    tower(n, a, b, c)

    // 当 n=1 时,移动次数为 1
    // 当 n=2 时,移动次数为 3
    // 当 n=3 时,移动次数为 7
    // 当 n=4 时,移动次数为 15
    fmt.Println(total)
}

// 表示将N个盘子,从 a 杆,借助 b 杆移到 c 杆
func tower(n int, a, b, c string) {
    if n == 1 {
        total = total + 1
        fmt.Println(a, "->", c)
        return
    }

    tower(n-1, a, c, b)
    total = total + 1
    fmt.Println(a, "->", c)
    tower(n-1, b, a, c)
}

通过归纳法,我们得知需要移动的次数为2的n次方-1
通过计算可以得知2的64次方-1=18446744073709551615
所以显然得到的这个记过告诉我们,这个算法不是很现实所以我们不使用此方法

什么是数据结构

数据结构,顾名思义就是存放数据的结构,也可以认为是存放数据的容器。比如你要寻找出1000个数字中最大值,首先就需要将这个1000个数字记在某些卡片上,然后对卡片进行排序。
大多数算法都需要组织数据,所以产生了数据结构。数据结构在计算机中,主要是用来实现各种算法的基础,当然数据结构本身也是算法的一部分。
基本的数据结构有:链表,栈和队列,树和图

  • 链表:把数据链接起来,关联起来,一个数据节点指向另外一个数据节点,像自然界的一条条铁链,大部分数据结构,都是由链表若干变种来表示。
  • 链表也可用数组来实现,但一般情况下,因为数组是连续的,在链表增加和删除节点是容易造成冗余,效果不佳。所以链表在不同编程语言实现是这样的:C,C++用指针实现,Java是用类实现,而Go是用结构体引用来实现。
  • 栈和队列,主要用来存储多个数据,只不过一个是先进后出,一个是先进先出。比如下压栈,先入栈的数据是最后才能出来,而我们熟知的队列,先排队的人肯定先获得服务。
  • 树和图,树就是一个树根节点,存放着数据,下面有很多子节点,也存放着数据,类比自然界的树。图则可以类比自然界的地图,多个点指向多个点,点和点之间有一条或多条边,而这些点存放着数据,边也可以存放数据,比如距离等

数据结构是算法的辅助,是为了更高效组织数据的结构,所以数据结构和算法其实密切联系。

什么叫好的数据结构和好的算法

学习算法是为了更好的节约资源,但是选择合适的算法很难。我们需要对其进行数学分析才能知道什么是好的算法,在计算机里,我们称这一过程为算法分析

什么是好的数据结构和好的算法

  1. 计算机资源是有限的,占用计算机资源越小的越好

  2. 人的生命是有限的,等待的时间越短越好

得出新的理论:时间和空间复杂度理论
算法**

  1. 计算机资源是有限的,占用计算机资源越小的越好

  2. 人的生命是有限的,等待的时间越短越好

得出新的理论:时间和空间复杂度理论

上一篇:大熊君大话NodeJS之开篇------Why NodeJS(将Javascript进行到底)


下一篇:JavaACOFramework的各个类介绍(part2 : Ant4AS类)