帮酷LOGO
  • 显示原文与译文双语对照的内容
A guide to get started in algorithms

  • 源代码名称:guide_to_algorithms
  • 源代码网址:http://www.github.com/andyttran/guide_to_algorithms
  • guide_to_algorithms源代码文档
  • guide_to_algorithms源代码下载
  • Git URL:
    git://www.github.com/andyttran/guide_to_algorithms.git
  • Git Clone代码到本地:
    git clone http://www.github.com/andyttran/guide_to_algorithms
  • Subversion代码到本地:
    $ svn co --depth empty http://www.github.com/andyttran/guide_to_algorithms
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
  • 算法介绍

    命令行目

    本指南的主要目标是让开发人员开始使用算法。 本指南将作为没有引入介绍算法课程或者需要基本算法设计的开发人员的路线图。

    此外,本指南还将为开发人员准备Outco程序以及他们的入学基础检查。

    的承诺和要求

    这里指南可以花费小时的25-100小时取决于你对算法的曝光。 为了让概念被内部化,请允许花足够的时间来练习周的2-4. 最好按照给定的结构按照给定的顺序进行操作。

    最低要求:

    • 使用编程语言( 比如,Java,JavaScript,python,ruby,objective-c,C++,C )的流利度
    • 非常熟悉 forwhile 循环等循环构造。
    • 对控制流 ifelseandor 有较强的了解
    • 数组:查找,插入,循环
    • 对象( 哈希): 查找,循环,插入
    • 方法中的特定语言
    • 数学:代数( 比如 。对数。指数。素数。幂)

    如果你缺少一些最低要求,那么我建议你去复习一下课程。 以下是一些令人愉快的建议:

    策略

    开发算法技巧的策略围绕着一些非常重要的概念,这些概念需要不断重复。 学生在获取概念 2 )的基础上,获得收费的知识,3英镑的测试了解其中某一概念的。

    但是有一种结构化的算法可以让你的生活更容易学习。 数学中,在采取更高级的类之前,你应该先做一些。 这些先决条件是以有组织的方式排列的,因这里在移动前不会跳过基本概念。

    同样的算法和数据结构。 有一个结构,你可以以学习的主题,将大大提高你的理解,如果你通过了算法。 以下是我建议你遵循的步骤:

    • 学习评估算法的效率( 复杂性)
    • 制定解决问题的过程
    • 学习基本算法模式
    • 学习基本数据结构
    • 投入实践
    • 轻松启动,更轻松
    • 跟踪和测量

    让我们逐步覆盖这些区域中的每一个。

    1评估效率

    评估算法的效率是真正开发能力解决挑战性算法的第一步。 如果无法度量算法的效率,如何比较一种方法的可伸缩性与另一种方法的可伸缩性。

    让我们从时间和空间复杂性开始。

    时间复杂度 - 度量计算量
    空间复杂度测量内存量

    解决算法所需的计算或者内存量是在输入缩放时测量 relative的输入大小。 记住,对于时间和空间复杂性,我们要衡量的是输入数据的

    我们使用 Big-O 符号来度量时间和空间复杂度。 Big-O 是衡量事物增长速度的一种数学方法。 Big-O 指的是最差的案例场景。 也就是说,如果我们为算法选择了最糟糕的输入,那么它需要多长时间? 关于 Big-O 还有更多技术细节,如何在学术界的vs 行业访问它,但目前我们应该等待以后进一步探讨这个主题。

    在进一步深入研究 Big-O 之前,先让我们先讨论一下输入。

    1.确定缩放的内容

    当你试图访问算法的时间复杂度或者空间复杂度时,请始终询问自己: 我的输入比例如何?

    :以下代码 below的:,什么是缩放?

    // Take in an integer and print its value functionprintInteger(num) {
     console.log(num);
    }
     

    如果答案是 num的英镑值,那么你的答案是正确的。 我们将把 num 本身的价值扩展到。

    让我们尝试另一个问题:
    :以下代码 below的:,什么是缩放?

    // Print the first item in the arrayfunctionprintFirst(arr) {
     console.log(arr[0]);
    }
     

    A: 在这种情况下,它的array的 如果给定 array 作为输入,它通常是数组的长度。

    它可以以使用不同类型的输入进行复杂,以下是一些输入类型和常见因素:

    正在缩放的输入公共因子
    整型数的大小
    字符串字符串长度
    数组数组长度
    LinkedList节点的数目:
    节点的数目:
    Hashtablekey-value 对的数目
    矩阵矩阵的宽度和高度
    图表顶点和边的数目

    声明:这些是可以缩放的'公用'因子。 有时有一些特殊的问题可能会有 LESS 明显的影响因素。

    1 b-时间和空间单位

    为了帮助你开始分析复杂性,你需要获得一个时间单位和空间单位的感知。

    时间

    • 时间单位可以是一个算术运算: 5 + 7
    • 或者打印内容:console.log('hello')
    • 或者实例化一个新变量: let name = 'foo';
    • 或者访问 array 中的项: arr[5]
    • 或者返回内容:return'foobar';

    空间

    • 空间单位可以创建单个新变量: var i = 1;
    • 或者创建空 array: var list = [];
    • 或者将新项目添加到列表中: list.push('foo');
    • 或者将 key-value 对添加到hashtable中: obj[foo] = 'bar';

    1.逐行分析行

    开始时,尝试逐行评估复杂性,并确定每行的复杂性。 然后总结每行的复杂性以得到总的。

    现在让我们从时间复杂度开始。

    回答下面的代码这两个问题:

    • 什么是缩放?
    • 每一行的操作量是多少?
    // print the first and last item in the arrayfunctionprintFirstLast(arr) {
     console.log(arr[0]);
     console.log(arr[arr.length-1]);
    }

    • 输入 array的长度正在缩放
    • 第一个 print 语句有 2个操作,第二个 print 语句有 4操作。 你知道为什么?

    下面是我们如何逐行标记计算的方法:

    // print the first and last item in the arrayfunctionprintFirstLast(arr) {
     console.log(arr[0]); // 2 console.log(arr[arr.length-1]); // 4}// total = 2 + 4 = 6

    第一个print语句有一个 array 访问,然后打印到控制台,所以这是 2操作。 第二个打印语句包括: 访问长度,从长度减去,访问索引,然后打印到控制台。 对于第二个打印语句,总计为 4.

    总共有 6个计算,我们认为这是 O(1) 时间复杂性。 阅读下一节来了解原因。

    1 Drop低阶术语和系数

    使用复杂性分析,在查找操作或者内存总量后,需要执行以下两项操作:

    • 删除较低的订单条件
    • 领先项前面的降系数。

    这是因为对于 Big-O 分析,我们只关心最大数量级。 当输入的大小非常大时,较低的术语会使 LESS 产生。 这里外,由于大量是用于 Big-O,我们不包括前面的前导项的系数。

    在前一个例子中,我们确定了该算法有 6个操作,用上面的两个条件来。

    • 6 是最低的( 并且唯一的术语)
    • 6 本身是常数项的系数,因此它被缩减为 1.

    因此函数 above的时间复杂度为 O(1) 或者常数时间

    O(1) 时间意味着什么? 这意味着当输入量保持恒定时,算法执行的运算量。 这是有意义的,因为无论输入 array 获得多大,函数 printFirstLast 仍然会花费大量的时间执行。

    让我们进一步了解以下 10个总计,并将它的减少到 Big-O的大小顺序。 你可能必须查阅一些幂定律。 如果你不确定对数术语与其他术语的比较,还可以查看 Big-O Cheetsheet 。

    PROBLEM SET 1:
    Reduce the following to it Big-O magnitude:
    1) 5 + N
    2) N + N^2
    3) 15N + 13N
    4) 10000
    5) log(N) + 1
    6) log(N) * 3 + 14N + 3
    7) Nlog(N) + 3N^2
    8) N^3 + log(N^4)
    9) N! + 180000N^2 
    10) 300N^5 + 15002^N + 3N

    ( 滚动到底部以获取这里问题集的答案。)

    1.循环有时是线性的,但并非总是线性

    循环 让我们探索循环。 大多数时候,当我们通过一个 Collection 进行输入时,我们将考虑这个循环是 O(N) 。

    确定这里算法的时间复杂度:

    // print each item in the array.functionprintAll(arr) {
     for(let i =0; i <arr.length; i++) {
     console.log(arr[i]);
     }
    }

    英镑:你可能猜到它的线性时间或者英镑 O(N) 。 是的,那是正确的。

    确定循环的操作是否具有线性顺序大小的原因。 让我们以更详细的方式来探索它。 当有循环时,我们必须将操作 inside 乘以循环的总次数循环运行的次数。

    // print each item in the array.functionprintAll(arr) {
     // 1 (initiating i to 0 is an operation)// the loop runs N iterationsfor(let i =0; i <arr.length; i++) { // 2 operations per break condition checkconsole.log(arr[i]); // 2 operations to print }
    }// total = 1 + N * (2 + 2) = 4N + 1 // reduce down to O(N) or linear time complexity

    循环有时循环可能比较棘手,尤其是在循环中。 你必须确实计算代码,以查看循环运行的次数和与输入成比例的次数。

    评估以下代码以获得时间复杂度:

    // print the first ten items in the arrayfunctionfirstTen(arr) {
     let i =0;
     while(i <10&& i <arr.length) {
     console.log(arr[10]); 
     i++;
     }
    }

    让我们逐行浏览代码行,记住我们有

    // print the first ten items in the arrayfunctionfirstTen(arr) {
     let i =0; // 1// maximum of 10 iterationswhile(i <10&& i <arr.length){ // 4 operations for each break condition checkconsole.log(arr[10]); // 2 operations to print i++; // 1 to increment }
    }// total = 1 + 10 * (4 + 2 + 1) = 71 // reduce down to O(1) or constant time complexity

    循环: 让我们评估前一个问题的细微变化。

    评估以下代码以获得时间复杂度:

    // print from the 11th to the last items in the array.functionafterTen(arr) {
     let i =11;
     while(i <arr.length) {
     console.log(arr[i]); 
     i++;
     }
    }

    让我们逐行浏览代码行,记住我们有

    // print from the 11th to the last items in the array.functionafterTen(arr) {
     let i =11; // 1// maximum of N-10 iterationswhile(i <arr.length){ // 2 operations for each break condition checkconsole.log(arr[i]); // 2 operations to print i++; // 1 to increment }
    }// total = 1 + (N - 10) * (2 + 2 + 1) = 5N + 51// reduce down to O(N) or Linear time complexity

    注意如果将问题从索引 11打印到 array的末尾,那么当输入变大时,in循环的迭代量。

    1.按块分析

    逐行分析是你开始时的好方法。 但你可以很快知道它并非总是必要的。 我们做了大量的工作来计算操作的确切数量,以减少它的后退。

    你可以通过在一个时间段内查看代码块的代码来加速你的分析,你可以加快你的分析速度,并基于的大小评估。

    让我们在几个问题上尝试一下。

    评估以下prblem以获得时间复杂度:

    // given an array of integers, return all the even items.functionevens(arr){
     let results = [];
     for(let i =0; i <arr.length; i++) {
     if(arr[i] %2===0) {
     results.push(arr[i]);
     }
     }
     return result;
    }

    让它分成块和使用数量。

    // given an array of integers, return all the even items.functionevens(arr){
     let results = []; // constantfor(let i =0; i <arr.length; i++) { // linearif(arr[i] %2===0) { // constant results.push(arr[i]); 
     }
     return result; // constant}

    这个循环是一个线性的操作块,因为有一个线性的迭代量和它的所有 inside 都是常数。 线性块是整个算法中最大的一个,因此我们有的O(N) 时间

    1 g 嵌套的vs-un循环

    小心不要错误地假设只是因为算法中有多个 for-loops,它自动的二次 O(n^2) 复杂性或者更多。 你应该记住的简单规则是:

    • 嵌套循环 multiply
    • 循环 add

    让我们浏览几个不同的例子并分析问题,看看嵌套的和嵌套的循环如何影响算法的整体复杂性。

    嵌套循环让我们看一个嵌套循环的问题:

    // print all values that have a matching pairsfunctionfindPairs(arr) {
     for (let i =0; i <arr.length; i++) {
     for (let j = i; j <arr.length; j++) {
     if(arr[i] === arr[j]) {
     console.log(i, 'is a pair');
     }
     }
     }
    }

    这里有一个嵌套的循环,让我们评估这个算法的时间复杂度:

    // print all values that have a matching pairsfunctionfindPairs(arr) {
     for (let i =0; i <arr.length; i++) { // linearfor (let j = i; j <arr.length; j++) { // linearif(arr[i] === arr[j]) { // constantconsole.log(i, 'is a pair');
     }
     }
     }
    }

    由于有两个嵌套循环,我们将线性。线性和常数相乘,以使二次( N^2 ) 时间复杂度。 注意第二个循环如何从索引 i 开始,并移动到 array的末尾。 第二个循环每次都变得越来越小。 由于平均迭代次数大约为 0.5 %,所以我们仍然考虑内部循环的线性。 由于我们无论如何都会降低系数,所以内部回路简化为线性。

    1 h-了解本机方法的复杂性

    如果你的语言有一个本地排序方法,你知道 behind 场景中会发生什么? 确定你花时间研究和查找你的语言使用的排序方法。 然后,对排序函数的时间和空间复杂度要求进行循环。

    母语的本地方法具有固有的时间和空间复杂性,你需要理解它们。 你可以以了解更多关于这些函数的时间和空间复杂性的一个好方法是自己编码一些。

    下面是一个JavaScript数组的示例列表:

    • 数组- 数组
    • 数组- 映射
    • array - forEach
    • 数组- 反向
    • 数组- 排序

    在其他语言中,你可以查找以下方法:

    • Java - ArrayList,HashMap
    • python - 列表,字典
    • ruby - array,对象

    这些数据结构相关的许多方法将比时间 O(1) 更昂贵,有些方法创建一个可以导致 O(N) 空间的新副本。

    使用以下问题尝试rewritting的一些本机方法:

    PROBLEM SET 2:
    You are given an collection based on your language, write a few functions that perform operations on this collection. Determine with the time complexity is for each solution.
    Based on your language, the collection will be in this format:
    JavaScript: Array
    Java: ArrayList
    Python: List
    Ruby: Array 
    Other: Dynamic Array
    1) indexOf: given a collection and a target value, return the index in 
    which the value at the index matches the target value. If there is no
    match, return -1.
    2) evens: given a collection of integers, return only the even 
    values in a new copy of the collection
    3) split: given a string of characters, return a collection with 
    each character separated into its own separate item.
    4) sum: given a collection of integers, return the sum of them

    解决方案正在建设

    1.了解数据结构方法的复杂性

    现在进入本网站: Big-O Cheatsheet,并查看它。 对于排序和数据结构,重要的是要注意平均时间复杂度。 如果将这些排序方法和数据结构应用于较大的算法中,那么平均是常用的。

    如果我们关注的是,那么为什么突然聚焦到的情形 senario? 因为在使用排序/数据结构方法时,整个算法的最坏情况通常与排序/数据结构方法不符。

    在以后的测试中,我们将进一步扩展,但是现在我们评估算法时,如果使用排序和数据结构方法,那么在评估较差情况时使用平均值是更常见的。 否则每次在散列表中查找键时,它都是 O(N),只发生在极罕见的senarios中。

    1.识别数量级的公共顺序

    下面是导致不同时间复杂度的算法和模式的一些常见示例。 当问题有关联约束时,使用约束作为算法最终可能出现的线索。

    声明:这些示例高度依赖于正在进行缩放的实际输入。

    输入常见示例
    常量:O ( 1 )array 访问,算术运算符
    对数:O ( 日志( N ) )二进制搜索,二进制搜索树检索/插入( 平衡)
    线性:O ( N )通过 array 或者hashtable循环
    拟线性:O ( Nlog ( N ) )快速排序,整理,堆
    二次:O ( N^2 )嵌套循环
    多项式:O ( N^C )深嵌套循环
    指数:O ( C^N )多重递归
    阶乘:O ( N ) !排列

    1 j on复杂性分析

    学习更多的知识。分析问题并评估你已经写出的代码。 通过这两个教程来获得更多关于问题的实践。 此外,从现在开始,你所编写的每种算法都应该。

    渐近表示法

    Rithm学习 Big-O 符号的介绍

    如何用 Justin Abrah计算 Big-O

    2学习基本算法模式

    算法模式的基本列表将帮助你在第一系列算法中进行进展。 基本算法需要了解如何使用数组和散列。嵌套循环和强逻辑控制( 。ifif-elseandor ) 。

    在施工

    3学习线性数据结构

    • 数组和动态数组: 从这里开始了解有关数组和动态数组的更多信息。 如果开开发展学习 python,ruby 或者者 JavaScript,可以能没有向基本的array 数据结构( 连续内存块) 公开。 让我们回到以前的时代,找出哪些数组真正在幕后。

    • 这是由于 python 。ruby 和JavaScript中的数据结构常常被忽略而忽略了这些线性数据结构。 理解它们是如何构造的,以及如何通过这些更多限制功能数据结构来理解它们仍然很重要。 通常我们会受到约束,学习使用这些约束使我们更意识到解决问题的方法。 从真正理解这些线性数据structues开始。

    更多的问题集将用于这些问题。

    *** 在构造 *** 下

    4.开发问题解决过程

    阅读以下 4点并询问你是否归因于某些或者全部挑战:

    • 我经常发现很难理解这个问题是什么。
    • 我可以理解问题,但我不确定从哪里开始,或者我只是空白。
    • 我可以以快速进入编码,但当我在逻辑中找到错误时,我的算法似乎会被破坏。
    • 我可以以在我的头上找到一个算法,我认为可以能是正确的,但是我不能正确地写出来。

    这些挑战是有更结构化的过程来解决问题的。 你要建立一个解决问题的框架。 这里框架将为你提供要检查的步骤和行项目列表,以确保:

    • 你正确地理解了这个问题
    • 你可以通过语音和可视化你的代码,并在高层次上讨论解决方案
    • 你可以分析你的解决方案以确定算法的有效性
    • 你可以将你的算法转换为你可以验证的代码

    你可以根据需要采用和修改一个示例框架,以适应你的问题解决方式:

    • 了解问题
    • 询问澄清问题
    • 获取输入,输出,约束( 时间/空间)
    • 获取示例案例,边缘条件
    • 阐明你必须使用哪些函数/方法
    • 解决方案的探索
    • ( 或者与面试官) 交流
    • 图表( 铅笔/纸或者白板上)
    • 解释幼稚的解决方案
    • 集思广益
    • 解决方案分析
    • 用于验证解决方案的复杂性分析
    • 验证解决方案边缘条件
    • 编码
    • Pseudocoding
    • 从伪代码中编码解决方案
    • 运行示例案例
    • 检查边缘条件

    开发问题解决过程的路线图

    • 采用框架并打印出参考步骤供参考。
    • 选择更容易的问题来练习你的框架( 每天两次) 。 专注于流程而不是算法。
    • 按照框架的步骤进行操作。 专注于在移动到下一步之前应用每一步。
    • 练习不同格式:白板,语法高亮显示文本编辑器和纯文本编辑器。
    • 每天练习你的框架,直到你可以执行没有打印的引用。

    5.实施实践

    练习容易的层次算法进入事物的凹槽。 记住上一节中的步骤。 拿一个记事本和铅笔,必要时准备好图表。 总的来说,你应该从这些资源中处理至少 15个问题:

    完成这些问题后,你应该在通过检查的基础上有一个不错的选择。 如果你要申请申请/申请,请联系 Outco Outreach团队

    6对中间概念的进展

    如果你想进步更多,那么这些概念就是你接下来应该解决的。 对于这些概念来说,它们很常见,对于过去的技术屏幕进行技术界面是至关重要的。

    算法模式

    数据结构

    实践

    在这里列出的难度级别的最小 20问题如下:

    7.跟踪和测量

    如果你正在访问,你需要评估在一定的时间内解决算法的能力,并可以能与另一端有关。 通过 mock 访谈让你进入压力设定面试。

    以下是你可以用来测试自己的一些资源:

    在施工

    8.final-注释

    算法不是你一夜之间学习的,它需要实践和一致性。 我希望你把这作为一个有用的起点。 我将在几周内扩大这个资源。 如果有问题,请联系我。

    如果你发现这个指南有用的话,请 ,请随时与任何能从本指南中获得价值的人分享。

    解决方案

    SOLUTIONS TO PROBLEM SET 1:
    Reduce the following to it Big-O magnitude:
    1) 5 + n//O(N)
    2) n + n^2//O(n^2)
    3) 15n + 13n//O(n) 
    4) 10000//O(1)
    5) log(n) + 1//O(log(n))
    6) log(n) * 3 + 14n + 3//O(n)
    7) nlog(n) + 3n^2//O(n^2)
    8) n^3 + log(n^4)//O(n^3)
    9) n! + 180000n^2//O(n!)
    10) 300n^5 + 15002^n + 3n//O(n^5)



    Copyright © 2011 HelpLib All rights reserved.    知识分享协议 京ICP备05059198号-3  |  如果智培  |  酷兔英语