Published on

算法是编程的基础2

Authors

复杂度分析

1. 只关注循环执行次数最多的一段代码

我刚才说了，大 O 这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以，我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。 为了便于你理解，我还拿前面的例子来说明。

int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}

其中第 2、3 行代码都是常量级的执行时间，与 n 的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第 4、5 行代码，所以这块代码要重点分析。前面我们也讲过，这两行代码被执行了 n 次，所以总的时间复杂度就是 O(n)。

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

我这里还有一段代码。你可以先试着分析一下，然后再往下看跟我的分析思路是否一样。

int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}

这个代码分为三部分，分别是求 sum_1、sum_2、sum_3。我们可以分别分析每一部分的时间复杂度，然后把它们放到一块儿，再取一个量级最大的作为整段代码的复杂度。 第一段的时间复杂度是多少呢？这段代码循环执行了 100 次，所以是一个常量的执行时间，跟 n 的规模无关。 这里我要再强调一下，即便这段代码循环 10000 次、100000 次，只要是一个已知的数，跟 n 无关，照样也是常量级的执行时间。当 n 无限大的时候，就可以忽略。尽管对代码的执行时间会有很大影响，但是回到时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，我们都可以忽略掉。因为它本身对增长趋势并没有影响。 那第二段代码和第三段代码的时间复杂度是多少呢？答案是 O(n) 和 O(n2)，你应该能容易就分析出来，我就不啰嗦了。 综合这三段代码的时间复杂度，我们取其中最大的量级。所以，整段代码的时间复杂度就为 O(n2)。也就是说：总的时间复杂度就等于量级最大的那段代码的时间复杂度。那我们将这个规律抽象成公式就是： 如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).

几种常见时间复杂度实例分析

虽然代码千差万别，但是常见的复杂度量级并不多。我稍微总结了一下，这些复杂度量级几乎涵盖了你今后可以接触的所有代码的复杂度量级。

线性表结构

数组 链表（单向、双向、循环） 特殊的线性表：栈 特殊的线性表：队列 编程技巧：递归

线性表分为顺序存储结构和链式存储结构

线性表的顺序存储结构

  • 优点：
    • 无需为表示表中元素之间的逻辑关系而增加额外的存储空间（有下标）
    • 可以快速的存＼取表中任意位置的元素
  • 缺点：
    • 插入和删除操作需要移动大量的元素，耗费时间
    • 当线性表长度变化较大时，难以确定存储空间的容量
    • 容易造成存储空间的＂碎片＂（申请空间是一整块申请的） Golang实现线性表顺序存取结构
package main
import (
    "errors"
    "fmt"
)
const MAX_LENGTH = 20 // 常量定义线性表最大长度
//　定义一个线性表顺序存储结构体
type LineList struct {
    MaxLength  int
    Length int
    LineListContent []interface{}
}
//　初始化一个线性表
func InitLineList () *LineList{
    return &LineList{MaxLength:MAX_LENGTH, LineListContent:make([]interface{},0,MAX_LENGTH)}
}
//　判断当前线性表是否为空
func (l LineList) IsEmpty() bool {
    if l.Length == 0{
        return true
    }
    return false
}
// 判断当前线性表是否满了
func (l LineList) IsFull() bool{
    if l.Length == l.MaxLength{
        return true
    }
    return false
}
// 判断索引是否越界，越界返回ｔｒｕｅ
func (l LineList) indexOver(i int) bool{
    if i < 1 || i >l.Length{
        return true
    }
    return false
}
// 获取一个ｎｏｄｅ数据
func (l LineList) getData(i int )(interface{},error){
    if ok:= l.indexOver(i); ok{
        return "",errors.New("查找的索引不在线性表范围内")
    }
    return l.LineListContent[i+1],nil
}
// 任意位置删除一个ｎｏｄｅ数据
func (l *LineList) Delete(i int)(interface{},error){
    if ok:= l.indexOver(i); ok{
        return "",errors.New("删除的索引不在线性表范围内")
    }
    if ok:=l.IsEmpty();ok{
        return  "",errors.New("空表没有可删除的数据")
    }
    deleteData := l.LineListContent[i-1]
    for j:=i-1; j<l.Length-1;j++{
        l.LineListContent[j] = l.LineListContent[j+1]
        fmt.Println(j,"个",l.LineListContent[j])
    }
    l.LineListContent = l.LineListContent[:l.Length-1] // 留了最后一个在，需要切除
    l.Length --
    return deleteData,nil
}
//末尾　ｐｏｐ　一个数据
func (l *LineList) Pop()(interface{},error){
    if ok:= l.IsEmpty();ok{
        return "",errors.New("空表，无法删除任何数据")
    }
    temp := l.LineListContent[l.Length-1]
    l.LineListContent = l.LineListContent[:l.Length-1]
    l.Length --
    return temp,nil
}
// 末尾　Append 一个数据
func (l *LineList) Append(data interface{})(bool,error){
    if ok:= l.IsFull(); ok{
        return false,errors.New("线性表已满，无法添加数据")
    }
    l.LineListContent = append(l.LineListContent, data)
    l.Length ++
    return true,nil
}
// 任意位置　ｉｎｓｅｒｔ　一个数据
func (l *LineList) Insert(i int,data interface{})(bool,error){
    if ok:= l.IsFull(); ok{
        return false,errors.New("线性表已满，无法添加数据")
    }
    if ok:= l.indexOver(i);ok{
        return false,errors.New("插入点越界")
    }
    l.Append("") // 增加一个空数据，防止下面访问越界
    for j:=l.Length-1;j>i-1;j--{
        //从后往前赋值，新增一个空ｎｏｄｅ，然后把数据一个个后移，直到插入的位置
        //知道线性表从１开始，而切片是从０开始的
        l.LineListContent[j] = l.LineListContent[j-1]
    }
    l.LineListContent[i-1] = data
    return true,nil
}
func main(){
    ls := InitLineList()
    ls.Append(11)
    fmt.Println(ls.LineListContent) //[11]
    fmt.Println(ls.Length) // 1
    ls.Insert(3,"gac")
    ls.Insert(1,"gac")
    fmt.Println(ls.LineListContent) //[gac 11]
    fmt.Println(ls.Length)  //2
    ls.Delete(2)
    fmt.Println(ls.LineListContent) //[gac]
    fmt.Println(ls.Length)     // 1
    cd,err0 := ls.Pop()
    if err0==nil{
        fmt.Println(cd)      // gac
    }
    fmt.Println(ls.LineListContent) //[]
    fmt.Println(ls.Length)    // 0
}

线性表的链式存储结构－－单链表

  • 特点：除了要存储数据元素信息外还要存储后继元素的存储地址（指针）数据域＋指针域＝存储映像（节点node）,因为此链表的每个节点中值包含一个指针域，所以叫做单链表
package main

import (
    "fmt"
)
type Node struct {
    data interface{}
    next *Node
}
// get the first Node
func (n *Node) getFirstNode() *Node{
    if n.next == nil{
        return nil
    }
    return n.next
}
// get the end Node
func (n *Node) getEndNode() *Node{
    if n.next == nil{
        return nil
    }
    for n.next != nil{
        n = n.next
    }
    return n
}
// Append a Node to linkList
func (n *Node) Append(data interface{})bool{
    // create a Node
     tempNode := &Node{data, nil}
     //i := n
     for n.next!=nil{
         n = n.next
     }
     n.next = tempNode
     return true
}
// find a Node
func (n *Node) getOneNode(i int)*Node{
    length := 0
    for n.next!=nil{
        length ++
        if i == length{
            return n.next
        }
        n = n.next
    }
    return nil
}
// delete a Node
func (n *Node) Delete(i int)*Node{
    length:=0
    for n.next!=nil{
        length ++
        if i == length{
            temp := n.next
            n.next = n.next.next
            return temp
        }
        n = n.next
    }
    return nil
}
// insert into the LinkList everywere
func (n *Node) Insert (i int ,data interface{}) bool {
    needAppend := &Node{ data ,nil}
    if i>n.getLinkLength() || i< 1{
        panic("插入位置错误")
        return false
    }
    length := 1
    for n.next != nil{
        if i == length{
            temp := n.next
            n.next = needAppend
            needAppend.next = temp
            return true
        }
    }
    return false
}
func (n *Node)getLinkLength()int{
    length := 0
    for n.next!=nil{
        length++
        n = n.next
    }
    return length
}
// map the LinkList all data
func (n *Node) MapTheLinkList(){
    length := n.getLinkLength()
    for i:=0;i<length; i++{
        fmt.Println(n.next.data)
        n = n.next
    }
}
func (n *Node) Clear() bool{
    if n.next == nil{
        return true
    }
    n.next = nil
    return true
}
// init a linkList
func initLinkList () *Node{
    return &Node{"the head node",nil}
}
func main(){
    li := initLinkList() // 初始化一个空单链表
    fmt.Println(li)      
    li.Append("aaa")  
    fmt.Println(li)
    li.Append("bbb")
    li.Append("ccc")
    li.Append("ddd")
    fmt.Println(*li.getFirstNode()) //{aaa 0xc04204a440}
    fmt.Println(*li.getEndNode())   //{ddd <nil>}
    fmt.Println(li.getLinkLength())  // 4
    fmt.Println("delete = ", li.Delete(1)) //delete =  &{aaa 0xc04204a440}
    fmt.Println(*li.getFirstNode())  //{bbb 0xc04204a460}
    fmt.Println(*li.getEndNode())    //{ddd <nil>}
    fmt.Println(li.getLinkLength())  // 3
    li.Append("eee")
    li.Append("ggg")
    li.MapTheLinkList()  // bbb ccc ddd eee ggg
    fmt.Println(li.getLinkLength())  //5
    li.Clear()  
    fmt.Println(li) //&{the head node <nil>}
}
  • 线性表的链式存储，以及使用快慢指针找不知长度链表的中间节点
package main

import (
    "fmt"
    "strconv"
)

// 定义一个node结构体
type Node struct {
    data string
    next *Node
}
func (n *Node) Append(data string){
    createNode := &Node{data,nil}
    for n.next != nil{
        n = n.next
    }
    n.next = createNode
}
func (n *Node) GetLength() int{
    if n.next==nil{
        return 0
    }
    length:= 0
    for n.next!=nil{
        length ++
        n = n.next
    }
    return length
}
func (n *Node) MapLinkList()[]string{
    var str []string
    if n.next == nil{
        return nil
    }
    for n.next != nil{
        str = append(str,n.next.data)
        n = n.next
    }
    return str
}
// 快慢指针法求不知道长度的链表的中间值
func (n *Node)GetCenterNode()[]string{
    str := make([]string,0,2)
    if n.next==nil{
        return nil
    }
    l := n.next
    s := n.next
    for s.next!= nil{
        // 单数情况
        if l.next==nil{
             str = append(str, s.data)
             return str
        }
        // 双数情况
        if l.next != nil && l.next.next == nil{
             str = append(str,s.data)
             str = append(str,s.next.data)
             return str
        }
        s =s.next
        l = l.next.next
    }
    return str
}

// 初始化一个链表
func initLinkList ()*Node{
    return &Node{"genesis node", nil}
}
func Rand20List(n *Node){
    for i:=0;i<3;i++{
        n.Append("this is "+strconv.Itoa(i))
    }
}

func main(){
    link := initLinkList()
    var s int
    for {
        fmt.Println("1.查看链表")
        fmt.Println("2.创建链表20个数据")
        fmt.Println("3.链表长度")
        fmt.Println("4.查看中间节点值")
        fmt.Println("5.退出")
        fmt.Println("请输入选择：")
        fmt.Scan(&s)
        switch s {
        case 1:
            fmt.Println(link.MapLinkList())
        case 2:
            Rand20List(link)
        case 3:
            fmt.Println(link.GetLength())
        case 4:
            fmt.Println(link.GetCenterNode())

        case 5:
            return

        }
    }
}
Discuss on Twitter • View on GitHub