《算法基础》——导读

**
前言
**
算法是使高效的程序成为可能的方法。它们解释了如何排列记录、搜索项、计算数值(比如质因子分解)、查找一个街道网络中的最短路径、确定可能通过通信网络的最大流。算法好坏的差别可能意味着是在一秒、一个小时内解决问题,还是永远也不能解决问题。
学习算法使你能建立有用的方法工具来解决具体的问题。它能帮助你理解在不同的情况下,哪个算法是最有效的,所以对于一个特定的问题,你就能选择最适合的算法。对某些数据而言性能优异的算法可能对其他的数据而言表现糟糕。所以知道如何选择一个最适合当前情况的算法是很重要的。
更重要的是,通过学习算法,你可以学习常规的问题解决技巧。即使你已知的任何算法都不能很好地适合当前的状况,你也可以把这些技巧应用到其他问题上。这些技巧让你从不同的角度看问题,使你能创造和分析自己的算法,从而解决你的问题,并且满足没有预料到的需求。
除了帮助你解决工作上的问题,这些技巧甚至会帮助你获得需要使用这些技巧的工作。许多大的科技公司,比如微软、谷歌、雅虎、IBM等公司都想要让他们的程序员理解算法和相关问题的解决技巧。其中,有些公司因为让面试者在面试中解决算法编程和逻辑难题而“臭名昭著”。
好的面试官不一定期待你解决每一个难题。事实上,当你没有解决某个难题时,他们可能会了解更多。最好的面试官想看到你如何处理一个不熟悉的问题,而不是想要看到答案。他们想看到你是举起双手说这个问题在面试中是不合理的,还是你分析了这个问题,并提出了一条有希望的推理来用算法解决这个问题。“天哪,我不知道。或许我要上网搜一下”将会是一个坏的答案。“看起来一个递归的分治法可能有用”将会是一个好得多的答案。
这是一本易读的计算机算法导论书。它描述了一些重要的传统算法,并且说明了每一个算法在什么时候是适合的。它解释了如何分析算法从而理解它们的行为。最重要的,它教会了你创造自己新算法的技巧。
这里是本书中描述的一些有用的算法:
数值算法,比如随机化、分解因式、处理质数、数值积分
熟练操作常见数据结构的方法,比如堆、树、平衡树、B树
排序和搜索
网络算法,比如最短路径、生成树、拓扑排序和流计算
这里是本书中解释的一些常规的问题解决技巧:
暴力或者穷举搜索
分治法
回溯法
递归
分支界限
贪心算法和爬山法
最小花费算法
缩小范围
启发式算法
为了帮助读者掌握这些算法,本书提供了一些练习,读者可以利用它们来探索自己的方法,以便修改书中的算法并把它们应用到新的情况中。这些练习也会帮助你巩固算法中的主要技巧。

目录

[第1章 算法基础知识
1.1 方法]()
1.2 算法和数据结构
1.3 伪代码
1.4 算法的特点
1.4.1 大O符号
1.4.2 常见的运行时间函数
1.4.3 可视化函数
1.5实际因素
1.6 总结
1.7 练习
[第2章 数值算法
2.1 随机化数据]()
2.1.1 随机数生成
2.1.2 随机化数组
2.1.3 生成不均匀分布
2.2 寻找最大公约数
2.3 求幂运算
2.4 有关素数的运算
2.4.1 寻找素数因子
2.4.2 寻找素数
2.4.3素性测试
2.5 进行数值积分
2.5.1 矩形规则
2.5.2梯形规则
2.5.3 自适应求积
2.5.4 蒙特卡罗积分
2.6 查找零
2.7 总结
2.8 练习
[第3章 链表
3.1 基本概念]()
3.2 单链表
3.2.1 遍历链表
3.2.2 查找单元格
3.2.3 使用哨兵
3.2.4 在开头添加单元格
3.2.5 在结尾添加单元格
3.2.6 在某个单元格后插入单元格
3.2.7 删除单元格
3.3 双向链表
3.4 有序链表
3.5 链表算法
3.5.1 复制链表
3.5.2 链表的插入排序
3.6 链表的选择排序
3.7 多线程链表
3.8 循环链表
3.8.1 标记单元格
3.8.2 使用散列表
3.8.3 链表回溯
3.8.4 反转链表
3.8.5 乌龟和兔子
3.8.6 双向链表中的循环问题
3.9 总结
3.10 练习

时间: 2024-11-05 14:38:04

《算法基础》——导读的相关文章

《深入理解Scala》——第1章,第1.2节当函数式编程遇见面向对象

1.2 当函数式编程遇见面向对象 深入理解Scala 函数式编程和面向对象编程是软件开发的两种不同途径.函数式编程并非什么新概念,在现代开发者的开发工具箱里也绝非是什么天外来客.我们将通过Java生态圈里的例子来展示这一点,主要来看Spring Application framework和Google Collections库.这两个库都在Java的面向对象基础上融合了函数式的概念,而如果我们把它们翻译成Scala,则会优雅得多.在深入之前,我们需要先理解面向对象编程和函数式编程这两个术语的含义

《深入理解Scala》——第1章,第1.4节与JVM的无缝集成

1.4 与JVM的无缝集成 深入理解Scala Scala的吸引力之一在于它与Java和JVM的无缝集成.Scala与Java有很强的兼容性,比如说Java类可以直接映射为Scala类.这种紧密联系使Java到Scala的迁移相当简单,但在使用Scala的一些高级特性时还是需要小心的,Scala有些高级特性是Java里没有的.在Scala语言设计时已经小心地考虑了与Java无缝交互的问题,用Java写的库,大部分可以直接照搬(as-is)到Scala里. 1.4.1 Scala调用Java 从S

《深入理解Scala》——第2章,第2.1节学习使用Scala交互模式(REPL)

第2章 核心规则深入理解Scala 本章包括的内容: • 使用Scala交互模式(Read Eval Print Loop 简称REPL) • 面向表达式编程 • 不变性(Immutability) • Option类 本章内容覆盖了每个新Scala开发者都需要知道的几个主题.本章不会深入到每个主题里,但是会讲到可以让你自己去接着探索的程度.你将学会使用REPL,学会如何利用这个工具做软件的快速原型开发.然后我们会学到面向表达式编程,并从另一个视角来看控制结构是怎么回事.在此基础上,我们来研究不

《深入理解Scala》——第1章,第1.3节静态类型和表达力

1.3 静态类型和表达力 深入理解Scala 开发人员中有一个误解,认为静态类型必然导致冗长的代码.之所以如此是因为很多继承自C的语言强制要求程序员必须在代码中多处明确地指定类型.随着软件开发技术和编译器理论的发展,情况已经改变.Scala利用了其中一些技术进步来减少样板(boilerplate)代码,保持代码简洁. Scala做了以下几个简单的设计决策,以提高代码表达力. • 把类型标注(type annotation)换到变量右边. • 类型推断. • 可扩展的语法. • 用户自定义的隐式转

《深入理解Scala》——第1章,第1.5节总结

1.5 总结 深入理解Scala 本章中,你学到了一些Scala的设计理念.设计Scala的初衷在于把不同语言中的多种概念融合起来.Scala融合了函数式和面向对象编程,尽管显然Java也已经这么做了.Scala精选其语法,极大地减少了语言中的繁冗之处,使一些强大的特性可以优雅地表达,比如类型推断.最后,Scala和Java能够紧密集成,而且运行在Java虚拟机上,这或许是让Scala变成一种实用选择的最重要的一点.几乎不花代价就可以把Scala用于我们的日常工作中. 因为Scala融合了多种概

《深入理解Scala》——第1章,第1.1节Scala一种混合式编程语言

第1章 Scala--一种混合式编程语言 Scala是一种将其他编程语言中的多种技巧融合为一的语言.Scala尝试跨越多种不同类型的语言,给开发者提供面向对象编程.函数式编程.富有表达力的语法.静态强类型和丰富的泛型等特性,而且全部架设于Java虚拟机之上.因此开发者使用Scala时可以继续使用原本熟悉的某种编程特性,但要发挥Scala的强大能力则需要结合使用这些有时候相互抵触的概念和特性,建立一种平衡的和谐.Scala对开发者的真正解放之处在于让开发者可以随意使用最适合手头上的问题的编程范式.

《深入理解Scala》——第2章,第2.2节优先采用面向表达式编程

2.2 优先采用面向表达式编程 深入理解Scala 面向表达式编程是个术语,意思是在代码中使用表达式而不用语句.表达式和语句的区别是什么?语句是可以执行的东西,表达式是可以求值的东西.在实践中这有什么意义呢?表达式返回值,语句执行代码,但是不返回值.本节我们将学习面向表达式编程的全部知识,并理解它对简化程序有什么帮助.我们也会看一下对象的可变性,以及可变性与面向表达式编程的关系. 作者注:语句VS表达式 语句是可以执行的东西,表达式是可以求值的东西. 表达式是运算结果为一个值的代码块.Scala

《深入理解Scala》——第2章,第2.3节优先选择不变性

2.3 优先选择不变性 深入理解Scala 编程中的不变性指对象一旦创建后就不再改变状态.这是函数式编程的基石之一,也是JVM上的面向对象编程的推荐实践之一.Scala也不例外,在设计上优先选择不变性,在很多场景中把不变性作为默认设置.对此,你可能一下子会不适应.本节中,我们将学到不变性对于判等问题和并发编程能提供什么帮助. Scala里首先要明白的是不变对象和不变引用(immutable referene)的区别.Scala里的所有变量都是指向对象的引用.把变量声明为val意味着它是个不变"引

《深入理解Scala》——第2章,第2.4节用None不用null

2.4 用None不用null深入理解Scala Scala在标准库里提供了scala.Option类,鼓励大家在一般编程时尽量不要使用null.Option可以视作一个容器,里面要么有东西,要么什么都没有.Option通过两个子类来实现此含义:Some和None.Some表示容器里有且仅有一个东西,None表示空容器,有点类似List的Nil的含义. 在Java和其他允许null的语言里,null经常作为一个占位符用于返回值,表示非致命的错误,或者表示一个变量未被初始化.Scala里,你可以用

《深入理解Scala》——第2章,第2.5节多态场景下的判等

2.5 多态场景下的判等 深入理解Scala 众所周知,为多态的面向对象系统定义合适的判等和散列方法是个特别难的过程.这是因为子类可能在整个过程中造成一些相当怪异的问题,尤其是当类型层次上有多个实体(concrete)级别的时候.一般来说,对于需要比引用判等更强的判等(译者注:比如需要判断对象内部数据)的类,最好避免多层实体类层次.这是什么意思呢?有些时候类只需要引用判等就够了.也就是说只要两个对象不是同一个实例就判为不等.但是如果我们需要判断两个不同实例是否相等,而且又有多层实体类层次(mul