数据结构思维 第二章 算法分析

第二章 算法分析

原文:Chapter 2 Analysis of Algorithms

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

我们在前面的章节中看到,Java 提供了两种实现List的接口,ArrayListLinkedList。对于一些应用,LinkedList更快;对于其他应用,ArrayList更快。

要确定对于特定的应用,哪一个更好,一种方法是尝试它们,并看看它们需要多长时间。这种称为“性能分析”的方法有一些问题:

  • 在比较算法之前,你必须实现这两个算法。
  • 结果可能取决于你使用什么样的计算机。一种算法可能在一台机器上更好;另一个可能在不同的机器上更好。
  • 结果可能取决于问题规模或作为输入提供的数据。

我们可以使用算法分析来解决这些问题中的一些问题。当它有效时,算法分析使我们可以比较算法而不必实现它们。但是我们必须做出一些假设:

  • 为了避免处理计算机硬件的细节,我们通常会识别构成算法的基本操作,如加法,乘法和数字比较,并计算每个算法所需的操作次数。
  • 为了避免处理输入数据的细节,最好的选择是分析我们预期输入的平均性能。如果不可能,一个常见的选择是分析最坏的情况。
  • 最后,我们必须处理一个可能性,一种算法最适合小问题,另一个算法适用于较大的问题。在这种情况下,我们通常专注于较大的问题,因为小问题的差异可能并不重要,但对于大问题,差异可能是巨大的。

这种分析适用于简单的算法分类。例如,如果我们知道算法A的运行时间通常与输入规模成正比,即n,并且算法B通常与n ** 2成比例,我们预计AB更快,至少对于n的较大值。

大多数简单的算法只能分为几类。

  • 常数时间:如果运行时间不依赖于输入的大小,算法是“常数时间”。例如,如果你有一个n个元素的数组,并且使用下标运算符([])来访问其中一个元素,则此操作将执行相同数量的操作,而不管数组有多大。
  • 线性:如果运行时间与输入的大小成正比,则算法为“线性”的。例如,如果你计算数组的和,则必须访问n个元素并执行n - 1个添加。操作的总数(元素访问和加法)为2 * n -1,与n成正比。
  • 平方:如果运行时间与n ** 2成正比,算法是“平方”的。例如,假设你要检查列表中的任何元素是否多次出现。一个简单的算法是将每个元素与其他元素进行比较。如果有n个元素,并且每个元素与n - 1个其他元素进行比较,则比较的总数是n ** 2 - n,随着n增长它与n ** 2成正比。

2.1 选择排序

例如,这是一个简单算法的实现,叫做“选择排序”(请见 http://thinkdast.com/selectsort):

public class SelectionSort {

    /**
     * Swaps the elements at indexes i and j.
     */
    public static void swapElements(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * Finds the index of the lowest value
     * starting from the index at start (inclusive)
     * and going to the end of the array.
     */
    public static int indexLowest(int[] array, int start) {
        int lowIndex = start;
        for (int i = start; i < array.length; i++) {
            if (array[i] < array[lowIndex]) {
                lowIndex = i;
            }
        }
        return lowIndex;
    }

    /**
     * Sorts the elements (in place) using selection sort.
     */
    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int j = indexLowest(array, i);
            swapElements(array, i, j);
        }
    }
}

第一个方法swapElements交换数组的两个元素。元素的是常数时间的操作,因为如果我们知道元素的大小和第一个元素的位置,我们可以使用一个乘法和一个加法来计算任何其他元素的位置,这都是常数时间的操作。由于swapElements中的一切都是恒定的时间,整个方法是恒定的时间。

第二个方法indexLowest从给定的索引start开始,找到数组中最小元素的索引。每次遍历循环的时候,它访问数组的两个元素并执行一次比较。由于这些都是常数时间的操作,因此我们计算什么并不重要。为了保持简单,我们来计算一下比较的数量。

  • 如果start0,则indexLowest遍历整个数组,并且比较的总数是数组的长度,我称之为n
  • 如果start1,则比较数为n - 1
  • 一般情况下,比较的次数是n - start,因此indexLowest是线性的。

第三个方法selectionSort对数组进行排序。它从0循环到n - 1,所以循环执行了n次。每次调用indexLowest然后执行一个常数时间的操作swapElements

第一次indexLowest被调用的时候,它进行n次比较。第二次,它进行n - 1比较,依此类推。比较的总数是

n + n−1 + n−2 + ... + 1 + 0 

这个数列的和是n(n+1)/2,它(近似)与n ** 2成正比;这意味着selectionSort是平方的。

为了得到同样的结果,我们可以将indexLowest看作一个嵌套循环。每次调用indexLowest时,操作次数与n成正比。我们调用它n次,所以操作的总数与n ** 2成正比。

2.2 大 O 表示法

所有常数时间算法属于称为O(1)的集合。所以,说一个算法是常数时间的另一个方法就是,说它是O(1)的。与之类似,所有线性算法属于O(n),所有二次算法都属于O(n ** 2)。这种分类算法的方式被称为“大 O 表示法”。

注意:我提供了一个大 O 符号的非专业定义。更多的数学处理请参见 http://thinkdast.com/bigo

这个符号提供了一个方便的方式,来编写通用的规则,关于算法在我们构造它们时的行为。例如,如果你执行线性时间算法,之后是常量算法,则总运行时间是线性的。表示“是...的成员”:

f ∈ O(n) && g ∈ O(1) => f + g ∈ O(n)

如果执行两个线性运算,则总数仍然是线性的:

f ∈ O(n) && g ∈ O(n) => f + g ∈ O(n)

事实上,如果你执行任何次数的线性运算,k,总数就是线性的,只要k是不依赖于n的常数。

f ∈ O(n) && k 是常数 => kf ∈ O(n)

但是,如果执行n次线性运算,则结果为平方:

f ∈ O(n) => nf ∈ O(n ** 2)

一般来说,我们只关心n的最大指数。所以如果操作总数为2 * n + 1,则属于O(n)。主要常数2和附加项1对于这种分析并不重要。与之类似,n ** 2 + 100 * n + 1000O(n ** 2)的。不要被大的数值分心!

“增长级别”是同一概念的另一个名称。增长级别是一组算法,其运行时间在同一个大 O 分类中;例如,所有线性算法都属于相同的增长级别,因为它们的运行时间为O(n)

在这种情况下,“级别”是一个团体,像圆桌骑士的阶级,这是一群骑士,而不是一种排队方式。因此,你可以将线性算法的阶级设想为一组勇敢,仗义,特别有效的算法。

2.3 练习 2

本章的练习是实现一个List,使用 Java 数组来存储元素。

在本书的代码库(请参阅 0.1 节)中,你将找到你需要的源文件:

  • MyArrayList.java包含List接口的部分实现。其中四个方法是不完整的;你的工作是填充他们。
  • MyArrayListTest.java包含 JUnit 测试,可用于检查你的工作。

你还会发现 Ant 构建文件build.xml。你应该可以从代码目录运行ant MyArrayList,来运行MyArrayList.java,其中包含一些简单的测试。或者你可以运行ant MyArrayListTest运行 JUnit 测试。

当你运行测试时,其中几个应该失败。如果你检查源代码,你会发现四条 TODO 注释,表示你应该填充的方法。

在开始填充缺少的方法之前,让我们来看看一些代码。这里是类定义,实例变量和构造函数。

public class MyArrayList<E> implements List<E> {
    int size;                    // keeps track of the number of elements
    private E[] array;           // stores the elements
    
    public MyArrayList() {
        array = (E[]) new Object[10];
        size = 0;
    }
}

正如注释所述,size跟踪MyArrayList中由多少元素,而且array是实际包含的元素的数组。

构造函数创建一个 10 个元素的数组,这些元素最初为null,并且size设为0。·大多数时候,数组的长度大于size,所以数组中由未使用的槽。

Java 的一个细节:你不能使用类型参数实例化数组;例如,这样不起作用:

array = new E [10];

要解决此限制,你必须实例化一个Object数组,然后进行类型转换。你可以在 http://thinkdast.com/generics 上阅读此问题的更多信息。

接下来,我们将介绍添加元素到列表的方法:

public boolean add(E element) {
    if (size >= array.length) {
        // make a bigger array and copy over the elements
        E[] bigger = (E[]) new Object[array.length * 2];
        System.arraycopy(array, 0, bigger, 0, array.length);
        array = bigger;
    } 
    array[size] = element;
    size++;
    return true;
}

如果数组中没有未使用的空间,我们必须创建一个更大的数组,并复制这些元素。然后我们可以将元素存储在数组中并递增size

为什么这个方法返回一个布尔值,这可能不明显,因为它似乎总是返回true。像之前一样,你可以在文档中找到答案:http://thinkdast.com/colladd。如何分析这个方法的性能也不明显。在正常情况下,它是常数时间的,但如果我们必须调整数组的大小,它是线性的。我将在 3.2 节中介绍如何处理这个问题。

最后,让我们来看看get;之后你可以开始做这个练习了。

public T get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    return array[index];
}

其实get很简单:如果索引超出范围,它会抛出异常; 否则读取并返回数组的元素。注意,它检查索引是否小于size,大于等于array.length,所以它不能访问数组的未使用的元素。

MyArrayList.java中,你会找到set的桩,像这样:

public T set(int index, T element) {
    // TODO: fill in this method.
    return null;
}

阅读set的文档,在 http://thinkdast.com/listset,然后填充此方法的主体。如果再运行MyArrayListTesttestSet应该通过。

提示:尽量避免重复索引检查的代码。

你的下一个任务是填充indexOf。像往常一样,你应该阅读 http://thinkdast.com/listindof 上的文档,以便你知道应该做什么。特别要注意它应该如何处理null

我提供了一个辅助方法equals,它将数组中的元素与目标值进行比较,如果它们相等,返回true(并且正确处理null),则 返回。请注意,此方法是私有的,因为它仅在此类中使用;它不是List接口的一部分。

完成后,再次运行MyArrayListTesttestIndexOf,以及依赖于它的其他测试现在应该通过。

只剩下两个方法了,你需要完成这个练习。下一个是add的重载版本,它接受下标并将新值存储在给定的下标处,如果需要,移动其他元素来腾出空间。

再次阅读 http://thinkdast.com/listadd 上的文档,编写一个实现,并运行测试进行确认。

提示:避免重复扩充数组的代码。

最后一个:填充remove的主体。文档位于 http://thinkdast.com/listrem。当你完成它时,所有的测试都应该通过。

一旦你的实现能够工作,将其与我的比较,你可以在 http://thinkdast.com/myarraylist 上找到它。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,864评论 6 494
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,175评论 3 387
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 159,401评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,170评论 1 286
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,276评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,364评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,401评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,179评论 0 269
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,604评论 1 306
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,902评论 2 328
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,070评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,751评论 4 337
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,380评论 3 319
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,077评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,312评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,924评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,957评论 2 351

推荐阅读更多精彩内容

  • 第三章 ArrayList 原文:Chapter 3 ArrayList 译者:飞龙 协议:CC BY-NC-S...
    布客飞龙阅读 375评论 0 4
  • 1、线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。栈是一种特殊的线性表,这种线性表只能在固定的...
    雾熏阅读 2,393评论 0 10
  • 算法和数据结构 [TOC] 算法 函数的增长 渐近记号 用来描述算法渐近运行时间的记号,根据定义域为自然数集$N=...
    wxainn阅读 1,060评论 0 0
  • 此刻孤独到底 此刻,家里静极了,能听到自己的心跳。这时脑子里时刻都在琢磨着我的使命,我的未来,我的脑子都快烧坏...
    暖暖的吧阅读 214评论 0 3
  • 雷电使我从睡梦中惊醒 从云层直劈而下,风声鹤唳 盖过了列车的鸣笛 重重撞击我久闭的眼瞳 神形坐定,刹想起 时间如此...
    長安之上阅读 163评论 0 1