go 语言数据结构与算法

分治法：把一个复杂问题分成两个或更多的相同或相似的子问题 直到子问题可以简单的直接求解，原问题的解即子问题的解的合并 分治法一般使用递归来求问题的解

递归

不断的调用它本身 这里举个求阶乘的例子 1234....*N

func Rescuvie(n int)int{
 if n==0{
 return 1
 }
 return n*Rescuvie(n-1)
}

这里函数会不断的调用自身，每次重复会使运算链条加长 系统不得不使用栈来进行数据保存和恢复

有一种尾递归的方式 尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算，效率将会极大的提高

二分查找

在一个已经排好序的数列，找出某个数

1,5,9,15,81,123,189,333

从上面排好序的数列中找出数字 189

思路：先拿排好序的数字的中位数与目标数字进行比较，如果大，就拿左边的中位数，如果小就拿右边的中位数，持续这种过程直到找到

这个题，我还有一种思路，使用切片和 map 来实现

算法的复杂度

分为时间复杂度和空间复杂度

一个实现了某个算法的程序：

• 如果计算的速度越快，那么这个算法的时间复杂度越低
• 如果占用的计算资源越小，那么空间复杂度越低

一些常用的时间复杂度：

• 常数时间复杂度:O(1)
• 对数时间复杂度:O(logn)
• 一次方复杂度：O(n)
• 一次方乘数复杂度：O(nlogn)
• 乘方复杂度：O(n^2),O(n^3)
• 指数复杂度：O(n!)
• 无线大复杂度:O(n^n)

p 和 NP 问题

单链表

每个节点保存数据和下一个节点的引用

双向链表

还有上一个节点的引用

循环链表

链表的尾节点指向头节点

双向循环链表

链表的头节点还指向尾节点，尾节点还指向头节点