算法分析
in 算法 with 0 comment

算法分析

in 算法 with 0 comment

code.png

算法分析

作者: times 时间: 2019/3/11

算法分析与分析基础

计算机系统中的任何软件都是按个个特定的算法来予以实现的。用什么方法来设计算法,如何判定一个算法的性能, 设计的算法需要多少运行时间、多少存储空间,这些问题都是在开发一个软件时必须考 虑的。算法性能的好坏,直接决定了软件性能的优劣。

本章将主要介绍算法、算法设计、算法分析的基本概念,以及常见重要问题的类型和常用算法的设计方法。

==算法设计常见的重要问题类型==

排序 查找 组合 几何 数值 其他

递归算法

递归算法是一种通过自身调用自身或间接调用自身来达到问题解决的算法。递归的基本思想是把个要求解的问题划分成一一个或多个规模更小的子问题, 这些规模更小的子问题应该与原问题保持同一类型, 然后用同样的方法求解规模更小的子问题。例如在”件产品中有1件次品的存在,所有产品的外形样而重量有差异,如何能尽快通过称重的方法将次品找出呢?最直观的解题思路是先将产品分为相等或相近的两组,进行称重后必然有一端重端轻, 此时还无法判断次品所在;然后继续对每部分的n12个产品再进行分组和称重,如果平衡则这部分的n2个产品都为正品,即次品在另外那部分中,否则次品就在这n/2个产品中。这样寻找次品的范围就减少了-半。依照这种方法不断缩小次品的范围,直到最后一对一找出次品。

处理重复性计算时,递归往往使函数的定义和算法的描述简单明了、易于理解、容易编程和验证。任何利用计算机求解的问题所需的计算时间与其规模是相关的。问题的规模越小,解题所需的时间通常也越小,从而较容易处理。因此很多复杂问题使用了递归技术能够给出非常直观的解法,结构简洁清晰,易于算法分析。在计算机软件领域,递归算法是不可或缺的。

汉诺塔问题

描述

汉诺塔问题(又称为河内塔问题),是一个大家熟知的问题。在A,B,C三根柱子上,有n个不同大小的圆盘(假设半径分别为1-n吧),一开始他们都叠在我A上(如图所示),你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。游戏中的每一步规则如下:

  1. 每一步只允许移动一个盘子(从一根柱子最上方到另一个柱子的最上方)
  2. 移动的过程中,你必须保证大的盘子不能在小的盘子上方(小的可以放在大的上面,最大盘子下面不能有任何其他大小的盘子)

图示:

image

样例

样例 1:

输入:n = 2
输出: ["from A to B","from A to C","from B to C"]

样例 2:

输入:n = 3
输出:["from A to C","from A to B","from C to B","from A to C","from B to A","from B to C","from A to C"]

参考答案

public class Solution {
    /**
     * @param n: the number of disks
     * @return: the order of moves
     */
    List<String> step;
    public List<String> towerOfHanoi(int n) {
        // write your code here
        List<String> result = new ArrayList<>();
        step = new ArrayList<>();
        step.add("from A to B");
        step.add("from A to C");
        step.add("from B to A");
        step.add("from B to C");
        step.add("from C to A");
        step.add("from C to B");
        hanoi(result, n, 'A', 'B', 'C');
        return result;
    }
    private void hanoi(List<String> result, int n, char a, char b, char c) {
        if (n == 1) {
            move(result, a, c);
        } else {
            hanoi(result, n - 1, a, c, b);
            move(result, a, c);
            hanoi(result, n - 1, b, a, c);
        }
    }
    private void move(List<String> result, char m, char n) {
        switch (m) {
            case 'A': result.add(step.get(n == 'B' ? 0 : 1)); break;
            case 'B': result.add(step.get(n == 'A' ? 2 : 3)); break;
            case 'C': result.add(step.get(n == 'A' ? 4 : 5)); break;
        }
    }
}

相关问题 N皇后问题 N皇后问题 II

分治算法

在计算机科学中,分治法是建基於多項分支遞歸的一种很重要的算法範式。 字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 这个技巧是很多高效算法的基础,如排序算法(快速排序、归并排序)、傅立叶变换(快速傅立叶变换)。

分治算法的基本思想和一般原则及它在排序问题、查找问题和组合问题中的应用。

常见的问题类型

归并排序 快速排序 折半排序 选择问题 最大字段和问题 棋盘覆盖问题

相关问题 第k大元素 摆动序列

贪心算法

又称贪婪算法,是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。 比如在旅行推销员问题中,如果旅行员每次都选择最近的城市,那这就是一种贪心算法。

常见的问题类型

背包问题 多机调度问题 单源最短路径问题 最小代价生成树

相关问题 无向图中的最短路径 平面最大矩形

动态规划算法

是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。

通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

常见的问题类型

最优二叉搜索树 近似串匹配问题 多段图问题 最长公共子序列 流水作业调度

相关问题 最大矩形 我能赢吗

回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。 回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。

常见的问题类型

装载问题 0/1 背包问题 n 皇后问题 图的m着色问题 子集和数问题 深度优先搜索 货郎(TSP)问题 最大团(MCP)问题 哈密顿环问题

相关问题 单词接龙 II 贴纸拼单词

分支限界算法

与贪婪算法一样,这种方法也是用来为组合优化问题设计求解算法的,所不同的是它在问题的整个可能解空间搜索,所设计出来的算法虽其时间复杂度比贪婪算法高,但它的优点是与穷举法类似,都能保证求出问题的最佳解,而且这种方法不是盲目的穷举搜索,而是在搜索过程中通过限界,可以中途停止对某些不可能得到最优解的子空间进一步搜索(类似于人工智能中的剪枝),故它比穷举法效率更高。

常见的问题类型

FIFO分支限界算法 LC分支限界算法 0/1 背包问题 带期限的作业排序 旅行商问题 单源点最短路径问题

相关问题 单词计数 (Map Reduce版本)


更多有趣题目

LintCode leetcode

Responses