也许只是在知乎闲逛心血来潮的看到了这篇文章 怎么学算法，突然意识到自己算法方面的薄弱。大学学习的就是计算机方面的专业，但是不管是C，C++，都没好好学过，更别说算法了，虽然我现在从事iOS开发~，从最开始入职工作，到意识深度学习提升个人价值，再到各类面试的问题，算法总是有围绕在身体，但是我从来都是刻意的去回避这些问题，导致我现在最基础的算法我都不能够很好应付。
年前看了 怎么学算法 之后，我毅然决然的买了两本算法书，《算法》（第四版），《算法导论》，我从《算法》开始，很多人都这个能为之后看算法导论打下一定基础（毕竟我的基础太差）。因为我的自律性一直不太好，以此记录，来督促自己保持学习的习惯。并且能够有所得，而不是吃了又吐回去。
算法
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
特征
一个算法应该具有以下五个重要的特征：
有穷性
（Finiteness）
算法的有穷性是指算法必须能在执行有限个步骤之后终止；
确切性
(Definiteness)
算法的每一步骤必须有确切的定义；
输入项
(Input)
一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
输出项
(Output)
一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
可行性
(Effectiveness)
算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。
要素
一，数据对象的运算和操作：计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类：
1，算术运算：加减乘除等运算
2，逻辑运算：或、且、非等运算
3，关系运算：大于、小于、等于、不等于等运算
4，数据传输：输入、输出、赋值等运算
二，算法的控制结构：一个算法的功能结构不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。
评定
同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。
T(n)=Ο(f(n))
因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。
空间复杂度
算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
正确性
算法的正确性是评价一个算法优劣的最重要的标准。
可读性
算法的可读性是指一个算法可供人们阅读的容易程度。
健壮性
健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性
基础部分
一.数据结构
主要学习了三种基础的抽象数据类型：背包、队列、栈。以及使用链表实现背包、队列、栈。
//基础 创建链表
class Node: NSObject {
var item:Any?
var next:Node?
}
//背包
class STBag: NSObject {
fileprivate var first:Node?
fileprivate var count:Int = 0
public func add(_ item:Optional<Any>){
if (first != nil)
{
let oldfirst = first
first = Node.init()
first!.item = item as AnyObject
first!.next = oldfirst
}
else
{
first = Node()
first?.item = item as AnyObject
}
count = count+1
}
func isEmpty() -> Bool {
return count != 0
}
func size() -> Int {
return count
}
}
//栈
class STStack: NSObject {
fileprivate var first:Node?
fileprivate var count:Int = 0
public func push(_ item:Optional<Any>){
if (first != nil)
{
let oldfirst = first
first = Node.init()
first!.item = item as AnyObject
first!.next = oldfirst
}
else
{
first = Node()
first?.item = item as AnyObject
}
count = count+1
}
public func peek()->Optional<Any>{
return first?.item
}
public func pop() -> Any?{
if (count>0)
{
let item = first?.item
first = first?.next
count = count - 1
return item
}
else
{
return nil
}
}
public func isEmpty() -> Bool {
return count != 0
}
public func size() -> Int {
return count
}
}
//队列
class STQueue: NSObject {
fileprivate var fisrt:Node?
fileprivate var last:Node?
fileprivate var count:Int = 0
public func enqueue(_ item:Optional<Any>){
if (count != 0){
let oldlast = last
last?.item = item
last?.next = nil
oldlast?.next = last
count = count + 1
}
else{
let itemNode = Node()
itemNode.item = item
last = itemNode
fisrt = last
count = count + 1
}
}
public func dequeue()->Node?{
if (count != 0){
let item = fisrt?.item
fisrt = fisrt?.next
count = count - 1
return item as? Node
}
else {
last = nil
return nil
}
}
public func isEmpty() -> Bool {
return count != 0
}
public func size() -> Int {
return count
}
}
二.算法分析
- 科学方法
- 细致观察特点，经过精确的测量
- 根据观察结果提出假设模型
- 根据模型预测未来的时间
- 继续观察并核实预测的准确性
- 反复知道确认预测和观察一致
- 观察
- 计时器
- 实验数据分析
- 数学模型
- 执行每条语句的耗时
- 执行每一条语句的频率
- 增长数量级的分类
- 常数级别
- 对数级别
- 线性级别
- 线性对数级别
- 平方级别
- 立方级别
- 指数级别
也许不是每天记录一堂算法学习记录，一定会以高频率的方式记录总结实践学习到知识
Demo地址：https://github.com/StoneAi/Algorithms
持续更新
网友评论