1 00:00:00,000 --> 00:00:05,830 2 00:00:05,830 --> 00:00:07,910 >> 所有的权利,所以,计算复杂度。 3 00:00:07,910 --> 00:00:10,430 只是有点警告 在我们深入太far-- 4 00:00:10,430 --> 00:00:13,070 这很可能是其中 最数学重的东西 5 00:00:13,070 --> 00:00:14,200 我们谈论的CS50。 6 00:00:14,200 --> 00:00:16,950 希望这将不会过于庞大 我们会尽力引导你 7 00:00:16,950 --> 00:00:19,200 通过的过程中,但 只是有点公平的警告。 8 00:00:19,200 --> 00:00:21,282 有一点点 数学这里涉及。 9 00:00:21,282 --> 00:00:23,990 好了,所以为了使 利用我们的计算资源 10 00:00:23,990 --> 00:00:28,170 在现实天下 - 这是真的 重要的是要了解算法 11 00:00:28,170 --> 00:00:30,750 以及如何处理数据。 12 00:00:30,750 --> 00:00:32,810 如果我们有一个非常 高效的算法, 13 00:00:32,810 --> 00:00:36,292 可的资源量最小化 我们可用来对付它。 14 00:00:36,292 --> 00:00:38,750 如果我们有一个算法, 是要采取了很多工作, 15 00:00:38,750 --> 00:00:41,210 处理一个真正 大量的数据,这是 16 00:00:41,210 --> 00:00:44,030 将需要更 和更多的资源,这 17 00:00:44,030 --> 00:00:47,980 就是金钱,RAM,所有的那种东西。 18 00:00:47,980 --> 00:00:52,090 >> 所以,能够分析一个 使用这种算法工具集, 19 00:00:52,090 --> 00:00:56,110 基本上,询问的问题 - 如何做到这一点的算法规模 20 00:00:56,110 --> 00:00:59,020 因为我们在它扔越来越多的数据? 21 00:00:59,020 --> 00:01:02,220 在CS50,数据量我们 有工作是非常小的。 22 00:01:02,220 --> 00:01:05,140 一般情况下,我们的节目会 在第二或less--运行 23 00:01:05,140 --> 00:01:07,830 大概少了很多 尤其是早期。 24 00:01:07,830 --> 00:01:12,250 >> 不过想想一个公司的交易 拥有亿万顾客。 25 00:01:12,250 --> 00:01:14,970 他们需要处理 客户数据。 26 00:01:14,970 --> 00:01:18,260 作为客户数量它们 有变得越来越大, 27 00:01:18,260 --> 00:01:21,230 这将需要 越来越多的资源。 28 00:01:21,230 --> 00:01:22,926 还有多少资源? 29 00:01:22,926 --> 00:01:25,050 嗯,这取决于如何 我们分析的算法, 30 00:01:25,050 --> 00:01:28,097 使用该工具箱中的工具。 31 00:01:28,097 --> 00:01:31,180 当我们谈论的复杂性 一种算法 - 有时你会 32 00:01:31,180 --> 00:01:34,040 听到它称为时间 复杂度和空间复杂度 33 00:01:34,040 --> 00:01:36,190 但我们正要 调用complexity-- 34 00:01:36,190 --> 00:01:38,770 我们通常讲 在最坏的情况。 35 00:01:38,770 --> 00:01:42,640 由于绝对最差桩 数据,我们可以扔吧, 36 00:01:42,640 --> 00:01:46,440 该算法将如何 处理或处理这些数据? 37 00:01:46,440 --> 00:01:51,450 我们一般称之为最坏情况下的 运行时的算法大O的。 38 00:01:51,450 --> 00:01:56,770 这样一种算法可能被说 在n或n邻邻运行平方。 39 00:01:56,770 --> 00:01:59,110 而更多的是什么 这意味着在第二。 40 00:01:59,110 --> 00:02:01,620 >> 然而,有时候,我们做护理 关于最好的情况。 41 00:02:01,620 --> 00:02:05,400 如果数据是一切我们想要的 它是,它是绝对完美 42 00:02:05,400 --> 00:02:09,630 和我们发送此完美 设置数据通过我们的算法。 43 00:02:09,630 --> 00:02:11,470 在这种情况下会如何处理? 44 00:02:11,470 --> 00:02:15,050 我们有时指的是作为 大欧米茄,所以在与大O相反, 45 00:02:15,050 --> 00:02:16,530 我们有大欧米茄。 46 00:02:16,530 --> 00:02:18,880 大欧米茄在最好的情况。 47 00:02:18,880 --> 00:02:21,319 大O在最坏的情况。 48 00:02:21,319 --> 00:02:23,860 一般情况下,当我们谈论 所述的算法的复杂性, 49 00:02:23,860 --> 00:02:26,370 我们正在谈论的 最坏的情况。 50 00:02:26,370 --> 00:02:28,100 所以记住这一点。 51 00:02:28,100 --> 00:02:31,510 >> 而在这个类中,我们通常会 到一边离开了严格的分析。 52 00:02:31,510 --> 00:02:35,350 有科学和领域 专门用于这种东西。 53 00:02:35,350 --> 00:02:37,610 当我们谈论的推理 通过算法, 54 00:02:37,610 --> 00:02:41,822 我们会做件逐件进行多 算法,我们谈论的类。 55 00:02:41,822 --> 00:02:44,780 我们真的只是在谈论 通过它推理常识, 56 00:02:44,780 --> 00:02:47,070 不与公式或证明, 或类似的东西。 57 00:02:47,070 --> 00:02:51,600 所以不要担心,我们不会 变成一个大的数学课。 58 00:02:51,600 --> 00:02:55,920 >> 所以我说,我们关心的复杂性 因为它要求的问题,怎么样 59 00:02:55,920 --> 00:03:00,160 做我们的算法处理大, 被扔在他们更大的数据集。 60 00:03:00,160 --> 00:03:01,960 那么,什么是数据集? 61 00:03:01,960 --> 00:03:03,910 什么我的意思是当我说? 62 00:03:03,910 --> 00:03:07,600 这意味着不管是什么让最 在上下文中意义上说,是诚实的。 63 00:03:07,600 --> 00:03:11,160 如果我们有一个算法,该 流程Strings--我们可能 64 00:03:11,160 --> 00:03:13,440 说起字符串的大小。 65 00:03:13,440 --> 00:03:15,190 这是该数据set-- 的大小,数量 66 00:03:15,190 --> 00:03:17,050 字符组成的字符串。 67 00:03:17,050 --> 00:03:20,090 如果我们谈论的 算法处理的文件, 68 00:03:20,090 --> 00:03:23,930 我们可能会谈论如何 千字节包含该文件。 69 00:03:23,930 --> 00:03:25,710 这就是今天的数据集。 70 00:03:25,710 --> 00:03:28,870 如果我们谈论的算法 处理数组更普遍, 71 00:03:28,870 --> 00:03:31,510 如排序算法 或搜索算法, 72 00:03:31,510 --> 00:03:36,690 我们可能谈论的数 的组成的阵列元素。 73 00:03:36,690 --> 00:03:39,272 >> 现在,我们可以测量 算法 - 特别是 74 00:03:39,272 --> 00:03:40,980 当我说我们可以 测量的算法,我 75 00:03:40,980 --> 00:03:43,840 意味着我们可以衡量 很多资源,它占用了。 76 00:03:43,840 --> 00:03:48,990 无论这些资源是多少 RAM--字节或兆字节的RAM 77 00:03:48,990 --> 00:03:49,790 它使用。 78 00:03:49,790 --> 00:03:52,320 或多少时间才能运行。 79 00:03:52,320 --> 00:03:56,200 我们可以把这种 测量,随意,F N的。 80 00:03:56,200 --> 00:03:59,420 其中n是数 在数据集中的元素。 81 00:03:59,420 --> 00:04:02,640 而F N是多少出头。 82 00:04:02,640 --> 00:04:07,530 有多少资源的单位呢 它要求以处理该数据。 83 00:04:07,530 --> 00:04:10,030 >> 现在,我们其实并不关心 什么F N的正是。 84 00:04:10,030 --> 00:04:13,700 事实上,我们很少will-- 肯定永远不会在这个分类 - 我 85 00:04:13,700 --> 00:04:18,709 潜入任何非常深 分析什么样的F n为。 86 00:04:18,709 --> 00:04:23,510 我们只是要谈论什么的F n近似或者什么也容易。 87 00:04:23,510 --> 00:04:27,600 和算法的倾向是 其最高阶项决定。 88 00:04:27,600 --> 00:04:29,440 我们可以看到我 意思是,通过采取 89 00:04:29,440 --> 00:04:31,910 一看一个更具体的例子。 90 00:04:31,910 --> 00:04:34,620 >> 所以我们可以说,我们有 三种不同的算法。 91 00:04:34,620 --> 00:04:39,350 其中第一个占据N 资源立方,一些单位 92 00:04:39,350 --> 00:04:42,880 处理规模为n的数据集。 93 00:04:42,880 --> 00:04:47,000 我们有第二个算法,需要 ñ立方加N的平方资源 94 00:04:47,000 --> 00:04:49,350 处理规模为n的数据集。 95 00:04:49,350 --> 00:04:52,030 而且我们有第三 算法运行in--的 96 00:04:52,030 --> 00:04:58,300 需要n个立方减去8N平方 加上20 N单位的资源 97 00:04:58,300 --> 00:05:02,370 处理的算法 与数据集大小为n的。 98 00:05:02,370 --> 00:05:05,594 >> 现在,再次,我们真的不打算 进入这种详细程度。 99 00:05:05,594 --> 00:05:08,260 我真的只是这些了 这里作为一个点的图示 100 00:05:08,260 --> 00:05:10,176 那我将是 使在第二,这 101 00:05:10,176 --> 00:05:12,980 是我们唯一真正关心 关于物联网的趋势 102 00:05:12,980 --> 00:05:14,870 随着数据集变得越来越大。 103 00:05:14,870 --> 00:05:18,220 因此,如果数据集为小,有 实际上是一个非常大的差异 104 00:05:18,220 --> 00:05:19,870 在这些算法。 105 00:05:19,870 --> 00:05:23,000 第三种算法有 需要13倍以上, 106 00:05:23,000 --> 00:05:27,980 资源的13倍的量 运行相对于第一个。 107 00:05:27,980 --> 00:05:31,659 >> 如果我们的数据集的大小为10,这 是大的,但不一定是巨大的, 108 00:05:31,659 --> 00:05:33,950 我们可以看到,有 其实有点区别。 109 00:05:33,950 --> 00:05:36,620 第三种算法 变得更加有效。 110 00:05:36,620 --> 00:05:40,120 这是关于实际上40% - 或60%更有效。 111 00:05:40,120 --> 00:05:41,580 需要40%的时间量。 112 00:05:41,580 --> 00:05:45,250 它可以run--它可以采取 400单位的资源 113 00:05:45,250 --> 00:05:47,570 处理规模10的数据集。 114 00:05:47,570 --> 00:05:49,410 而第一 算法,相比之下, 115 00:05:49,410 --> 00:05:54,520 需要1000单位的资源 处理规模10的数据集。 116 00:05:54,520 --> 00:05:57,240 但是,看看会发生什么的 我们的数字得到更大。 117 00:05:57,240 --> 00:05:59,500 >> 现在,所不同的 这些算法之间 118 00:05:59,500 --> 00:06:01,420 开始变得有点不那么明显。 119 00:06:01,420 --> 00:06:04,560 而事实上,有 低阶terms--或者说, 120 00:06:04,560 --> 00:06:09,390 低exponents--条款 开始变得无关紧要。 121 00:06:09,390 --> 00:06:12,290 如果数据集是大小 1000和第一算法 122 00:06:12,290 --> 00:06:14,170 运行在一个十亿步骤。 123 00:06:14,170 --> 00:06:17,880 和第二算法在运行 一个十亿和一百万的步骤。 124 00:06:17,880 --> 00:06:20,870 而第三个算法运行 在略低于一十亿步骤。 125 00:06:20,870 --> 00:06:22,620 这几乎是一个十亿步骤。 126 00:06:22,620 --> 00:06:25,640 那些低阶项启动 要成为真正无关紧要。 127 00:06:25,640 --> 00:06:27,390 而就真的 锤回家的point-- 128 00:06:27,390 --> 00:06:31,240 如果输入的数据是大​​小 million--所有这三个几乎 129 00:06:31,240 --> 00:06:34,960 采取一quintillion--如果 我的数学是correct--步骤 130 00:06:34,960 --> 00:06:37,260 以处理的数据输入 规模百万。 131 00:06:37,260 --> 00:06:38,250 这是一个很大的步骤。 132 00:06:38,250 --> 00:06:42,092 而事实上,他们中的一个可能 采取一对夫妇10万或一对夫妇100 133 00:06:42,092 --> 00:06:44,650 万元甚至更少的时候 我们谈论了许多 134 00:06:44,650 --> 00:06:46,990 这big--它是一种无关紧要的。 135 00:06:46,990 --> 00:06:50,006 他们都倾向于采取 大约ñ立方, 136 00:06:50,006 --> 00:06:52,380 所以我们实际上是指 所有这些算法 137 00:06:52,380 --> 00:06:59,520 作为n的顺序上 立方或大,O n立方的。 138 00:06:59,520 --> 00:07:03,220 >> 下面是一些比较列表 常见的计算复杂性类 139 00:07:03,220 --> 00:07:05,820 我们会遇到 算法,一般。 140 00:07:05,820 --> 00:07:07,970 而在CS50还专门。 141 00:07:07,970 --> 00:07:11,410 这些是从订购 通常最快在顶部, 142 00:07:11,410 --> 00:07:13,940 到通常最慢的下方。 143 00:07:13,940 --> 00:07:16,920 因此,固定的时间算法往往 是最快的,而不管 144 00:07:16,920 --> 00:07:19,110 的大小的 数据输入你通过研究。 145 00:07:19,110 --> 00:07:23,760 他们总是需要一个操作或 资源的一个单位来处理。 146 00:07:23,760 --> 00:07:25,730 它可能是2,它可能 是3,它可能是4。 147 00:07:25,730 --> 00:07:26,910 但这是一个常数。 148 00:07:26,910 --> 00:07:28,400 它不改变。 149 00:07:28,400 --> 00:07:31,390 >> 对数时间算法 是略胜一筹。 150 00:07:31,390 --> 00:07:33,950 而一个真正的好例子 对数时间算法 151 00:07:33,950 --> 00:07:37,420 你一定已经被看到现在是 撕裂电话簿 152 00:07:37,420 --> 00:07:39,480 找到迈克·史密斯在电话簿。 153 00:07:39,480 --> 00:07:40,980 我们切成两半的问题。 154 00:07:40,980 --> 00:07:43,580 所以,当n变大 和更大和larger-- 155 00:07:43,580 --> 00:07:47,290 其实,每次增加一倍 N,只需要一个步骤。 156 00:07:47,290 --> 00:07:49,770 所以这是好了很多 比说,线性时间。 157 00:07:49,770 --> 00:07:53,030 这是你的两倍N,它 采取的步骤数量的两倍。 158 00:07:53,030 --> 00:07:55,980 如果你三倍N,它需要 三倍的步骤的数量。 159 00:07:55,980 --> 00:07:58,580 每单位的一个步骤。 160 00:07:58,580 --> 00:08:01,790 >> 然后,事情变得有点缓慢 - 从那里少一点大。 161 00:08:01,790 --> 00:08:06,622 你有线性的节奏,时而 所谓的对数线性时间或只是N日志ñ。 162 00:08:06,622 --> 00:08:08,330 我们会为例 的算法的那 163 00:08:08,330 --> 00:08:13,370 运行中的n log N,这仍然是更好的 比二次时间 - ñ平方。 164 00:08:13,370 --> 00:08:17,320 或者多项式时间,n两个 任何数目大于2。 165 00:08:17,320 --> 00:08:20,810 或指数的时间,这 甚至worse-- C到n个。 166 00:08:20,810 --> 00:08:24,670 因此,一些常数提高到 输入的大小的功率。 167 00:08:24,670 --> 00:08:28,990 所以,如果有1,000--如果 数据输入是大小1000, 168 00:08:28,990 --> 00:08:31,310 它会采取C到第1,000权力。 169 00:08:31,310 --> 00:08:33,559 这是一个很多比多项式时间差。 170 00:08:33,559 --> 00:08:35,030 >> 阶乘时间更是雪上加霜。 171 00:08:35,030 --> 00:08:37,760 而事实上,也确实 有无限的时间算法, 172 00:08:37,760 --> 00:08:43,740 例如,所谓的愚蠢类别 - 其 工作是随机洗牌数组 173 00:08:43,740 --> 00:08:45,490 然后检查 无论是排序。 174 00:08:45,490 --> 00:08:47,589 如果它不是,随机 再次洗牌阵列 175 00:08:47,589 --> 00:08:49,130 并检查是否它的排序。 176 00:08:49,130 --> 00:08:51,671 正如你可能imagine-- 你能想象一个情况 177 00:08:51,671 --> 00:08:55,200 其中在最坏的情况下,这种意愿 从来没有真正开始的数组。 178 00:08:55,200 --> 00:08:57,150 该算法将永远运行。 179 00:08:57,150 --> 00:08:59,349 因此,这将是一个 无限时间的算法。 180 00:08:59,349 --> 00:09:01,890 希望你会不会写 任何因子或无限的时间 181 00:09:01,890 --> 00:09:04,510 算法CS50。 182 00:09:04,510 --> 00:09:09,150 >> 那么,让我们多了几分 具体看一些简单的 183 00:09:09,150 --> 00:09:11,154 计算复杂性类。 184 00:09:11,154 --> 00:09:13,070 因此,我们有一个example-- 两个例子这里 - 185 00:09:13,070 --> 00:09:15,590 恒定时间算法, 它始终以 186 00:09:15,590 --> 00:09:17,980 在最坏的情况下,单一的操作。 187 00:09:17,980 --> 00:09:20,050 因此,第一个example-- 我们有一个函数 188 00:09:20,050 --> 00:09:23,952 所谓的4对你来说,这 取大小1000的数组。 189 00:09:23,952 --> 00:09:25,660 但后来显然 实际上不看 190 00:09:25,660 --> 00:09:29,000 在它 - 并不真正关心什么 里面那个阵吧。 191 00:09:29,000 --> 00:09:30,820 永远只是返回四个。 192 00:09:30,820 --> 00:09:32,940 所以,这算法, 尽管事实上,它 193 00:09:32,940 --> 00:09:35,840 需要1000元不 做他们什么。 194 00:09:35,840 --> 00:09:36,590 刚刚返回四个。 195 00:09:36,590 --> 00:09:38,240 它总是一个步骤。 196 00:09:38,240 --> 00:09:41,600 >> 其实,加2 nums--这 我们以前作为well--见过 197 00:09:41,600 --> 00:09:43,680 只是处理两个整数。 198 00:09:43,680 --> 00:09:44,692 这不是一个单一的步骤。 199 00:09:44,692 --> 00:09:45,900 它实际上是一对夫妇的步骤。 200 00:09:45,900 --> 00:09:50,780 你得到了,你就会得到B,你加他们 在一起,你的输出结果。 201 00:09:50,780 --> 00:09:53,270 因此,这84步。 202 00:09:53,270 --> 00:09:55,510 但是,它总是不断的, 不管a或b。 203 00:09:55,510 --> 00:09:59,240 你要得到一个,拿到B,加 在一起,输出其结果。 204 00:09:59,240 --> 00:10:02,900 所以这是一个恒定的时间算法。 205 00:10:02,900 --> 00:10:05,170 >> 这里有一个例子 线性时间算法 - 206 00:10:05,170 --> 00:10:08,740 这gets--接受一个算法 一个附加步骤,可能的话, 207 00:10:08,740 --> 00:10:10,740 作为输入增长了1。 208 00:10:10,740 --> 00:10:14,190 因此,我们说,我们正在寻找 数5内的阵列。 209 00:10:14,190 --> 00:10:16,774 你可能会遇到这样的情况 你可以找到它相当早。 210 00:10:16,774 --> 00:10:18,606 但你也可以有 的情况下它 211 00:10:18,606 --> 00:10:20,450 可能是该阵列的最后一个元素。 212 00:10:20,450 --> 00:10:23,780 在大小5,数组,如果 我们正在寻找的数字5。 213 00:10:23,780 --> 00:10:25,930 这将需要5个步骤。 214 00:10:25,930 --> 00:10:29,180 而事实上,想象有 不随地5此数组中。 215 00:10:29,180 --> 00:10:32,820 我们实际上仍然要看看 该阵列的每一个元素 216 00:10:32,820 --> 00:10:35,550 为了确定 无论是否5是存在的。 217 00:10:35,550 --> 00:10:39,840 >> 因此,在最坏情况下,这是 该元素是最后一个阵列中 218 00:10:39,840 --> 00:10:41,700 或不存在的。 219 00:10:41,700 --> 00:10:44,690 我们还是来看看 所有的n个元素。 220 00:10:44,690 --> 00:10:47,120 因此该算法 以线性时间运行。 221 00:10:47,120 --> 00:10:50,340 您可以确认通过 说外推一点点, 222 00:10:50,340 --> 00:10:53,080 如果我们有一个6-元件阵列和 我们正在寻找5号, 223 00:10:53,080 --> 00:10:54,890 它可能需要6个步骤。 224 00:10:54,890 --> 00:10:57,620 如果我们有一个7-元件阵列和 我们正在寻找的数字5。 225 00:10:57,620 --> 00:10:59,160 这可能需要7个步骤。 226 00:10:59,160 --> 00:11:02,920 当我们增加一个元素,我们的 阵列,它需要一个步骤。 227 00:11:02,920 --> 00:11:06,750 这是一个线性算法 在最坏的情况下。 228 00:11:06,750 --> 00:11:08,270 >> 夫妇简单的问题给你。 229 00:11:08,270 --> 00:11:11,170 什么是runtime--什么 最坏情况下的运行时 230 00:11:11,170 --> 00:11:13,700 的代码,这个特殊的片段? 231 00:11:13,700 --> 00:11:17,420 所以我有一个4环路这里运行 从第j等于0,一路为m。 232 00:11:17,420 --> 00:11:21,980 而我所看到这里,是, 循环体运行在固定的时间。 233 00:11:21,980 --> 00:11:24,730 因此,使用术语 我们已经谈过about--什么 234 00:11:24,730 --> 00:11:29,390 将是最坏的情况 该算法的运行时间? 235 00:11:29,390 --> 00:11:31,050 拿第二。 236 00:11:31,050 --> 00:11:34,270 环路的内侧部分 运行在固定的时间。 237 00:11:34,270 --> 00:11:37,510 和的外侧部分 回路将运行的m倍。 238 00:11:37,510 --> 00:11:40,260 那么什么是最坏的情况下运行吗? 239 00:11:40,260 --> 00:11:43,210 你猜大O m的? 240 00:11:43,210 --> 00:11:44,686 你是对的。 241 00:11:44,686 --> 00:11:46,230 >> 要不要再来一个? 242 00:11:46,230 --> 00:11:48,590 这一次,我们有一个 环路的环路的内侧。 243 00:11:48,590 --> 00:11:50,905 我们有一个外环 运行从零到第 244 00:11:50,905 --> 00:11:54,630 我们有一个运行内环 从零到p和的里面, 245 00:11:54,630 --> 00:11:57,890 予指出,人体的 环在固定时间内运行。 246 00:11:57,890 --> 00:12:02,330 那么,什么是最坏情况下的运行时间 的代码,这个特殊的片段? 247 00:12:02,330 --> 00:12:06,140 好了,再次,我们有一个 运行P乘以外环。 248 00:12:06,140 --> 00:12:09,660 而且每个时间 - 迭代 该循环,而。 249 00:12:09,660 --> 00:12:13,170 我们有一个内环 也运行P乘以。 250 00:12:13,170 --> 00:12:16,900 然后那里面,还有的 恒时间 - 小片段存在。 251 00:12:16,900 --> 00:12:19,890 >> 因此,如果我们有一个外循环 运行P乘以其内部是 252 00:12:19,890 --> 00:12:22,880 内环那 运行p times--是什么 253 00:12:22,880 --> 00:12:26,480 最坏情况下的运行时 这个代码片段? 254 00:12:26,480 --> 00:12:30,730 你猜大O的P平方? 255 00:12:30,730 --> 00:12:31,690 >> 我是道格·劳埃德。 256 00:12:31,690 --> 00:12:33,880 这是CS50。 257 00:12:33,880 --> 00:12:35,622