>> 所有的权利，所以，计算复杂度。
只是有点警告 在我们深入太far--
这很可能是其中 最数学重的东西
我们谈论的CS50。
希望这将不会过于庞大 我们会尽力引导你
通过的过程中，但 只是有点公平的警告。
有一点点 数学这里涉及。
好了，所以为了使 利用我们的计算资源
在现实天下 - 这是真的 重要的是要了解算法
以及如何处理数据。
如果我们有一个非常 高效的算法，
可的资源量最小化 我们可用来对付它。
如果我们有一个算法， 是要采取了很多工作，
处理一个真正 大量的数据，这是
将需要更 和更多的资源，这
就是金钱，RAM，所有的那种东西。
>> 所以，能够分析一个 使用这种算法工具集，
基本上，询问的问题 - 如何做到这一点的算法规模
因为我们在它扔越来越多的数据？
在CS50，数据量我们 有工作是非常小的。
一般情况下，我们的节目会 在第二或less--运行
大概少了很多 尤其是早期。
>> 不过想想一个公司的交易 拥有亿万顾客。
他们需要处理 客户数据。
作为客户数量它们 有变得越来越大，
这将需要 越来越多的资源。
还有多少资源？
嗯，这取决于如何 我们分析的算法，
使用该工具箱中的工具。
当我们谈论的复杂性 一种算法 - 有时你会
听到它称为时间 复杂度和空间复杂度
但我们正要 调用complexity--
我们通常讲 在最坏的情况。
由于绝对最差桩 数据，我们可以扔吧，
该算法将如何 处理或处理这些数据？
我们一般称之为最坏情况下的 运行时的算法大O的。
这样一种算法可能被说 在n或n邻邻运行平方。
而更多的是什么 这意味着在第二。
>> 然而，有时候，我们做护理 关于最好的情况。
如果数据是一切我们想要的 它是，它是绝对完美
和我们发送此完美 设置数据通过我们的算法。
在这种情况下会如何处理？
我们有时指的是作为 大欧米茄，所以在与大O相反，
我们有大欧米茄。
大欧米茄在最好的情况。
大O在最坏的情况。
一般情况下，当我们谈论 所述的算法的复杂性，
我们正在谈论的 最坏的情况。
所以记住这一点。
>> 而在这个类中，我们通常会 到一边离开了严格的分析。
有科学和领域 专门用于这种东西。
当我们谈论的推理 通过算法，
我们会做件逐件进行多 算法，我们谈论的类。
我们真的只是在谈论 通过它推理常识，
不与公式或证明， 或类似的东西。
所以不要担心，我们不会 变成一个大的数学课。
>> 所以我说，我们关心的复杂性 因为它要求的问题，怎么样
做我们的算法处理大， 被扔在他们更大的数据集。
那么，什么是数据集？
什么我的意思是当我说？
这意味着不管是什么让最 在上下文中意义上说，是诚实的。
如果我们有一个算法，该 流程Strings--我们可能
说起字符串的大小。
这是该数据set-- 的大小，数量
字符组成的字符串。
如果我们谈论的 算法处理的文件，
我们可能会谈论如何 千字节包含该文件。
这就是今天的数据集。
如果我们谈论的算法 处理数组更普遍，
如排序算法 或搜索算法，
我们可能谈论的数 的组成的阵列元素。
>> 现在，我们可以测量 算法 - 特别是
当我说我们可以 测量的算法，我
意味着我们可以衡量 很多资源，它占用了。
无论这些资源是多少 RAM--字节或兆字节的RAM
它使用。
或多少时间才能运行。
我们可以把这种 测量，随意，F N的。
其中n是数 在数据集中的元素。
而F N是多少出头。
有多少资源的单位呢 它要求以处理该数据。
>> 现在，我们其实并不关心 什么F N的正是。
事实上，我们很少will-- 肯定永远不会在这个分类 - 我
潜入任何非常深 分析什么样的F n为。
我们只是要谈论什么的F n近似或者什么也容易。
和算法的倾向是 其最高阶项决定。
我们可以看到我 意思是，通过采取
一看一个更具体的例子。
>> 所以我们可以说，我们有 三种不同的算法。
其中第一个占据N 资源立方，一些单位
处理规模为n的数据集。
我们有第二个算法，需要 ñ立方加N的平方资源
处理规模为n的数据集。
而且我们有第三 算法运行in--的
需要n个立方减去8N平方 加上20 N单位的资源
处理的算法 与数据集大小为n的。
>> 现在，再次，我们真的不打算 进入这种详细程度。
我真的只是这些了 这里作为一个点的图示
那我将是 使在第二，这
是我们唯一真正关心 关于物联网的趋势
随着数据集变得越来越大。
因此，如果数据集为小，有 实际上是一个非常大的差异
在这些算法。
第三种算法有 需要13倍以上，
资源的13倍的量 运行相对于第一个。
>> 如果我们的数据集的大小为10，这 是大的，但不一定是巨大的，
我们可以看到，有 其实有点区别。
第三种算法 变得更加有效。
这是关于实际上40％ - 或60％更有效。
需要40％的时间量。
它可以run--它可以采取 400单位的资源
处理规模10的数据集。
而第一 算法，相比之下，
需要1000单位的资源 处理规模10的数据集。
但是，看看会发生什么的 我们的数字得到更大。
>> 现在，所不同的 这些算法之间
开始变得有点不那么明显。
而事实上，有 低阶terms--或者说，
低exponents--条款 开始变得无关紧要。
如果数据集是大小 1000和第一算法
运行在一个十亿步骤。
和第二算法在运行 一个十亿和一百万的步骤。
而第三个算法运行 在略低于一十亿步骤。
这几乎是一个十亿步骤。
那些低阶项启动 要成为真正无关紧要。
而就真的 锤回家的point--
如果输入的数据是大​​小 million--所有这三个几乎
采取一quintillion--如果 我的数学是correct--步骤
以处理的数据输入 规模百万。
这是一个很大的步骤。
而事实上，他们中的一个可能 采取一对夫妇10万或一对夫妇100
万元甚至更少的时候 我们谈论了许多
这big--它是一种无关紧要的。
他们都倾向于采取 大约ñ立方，
所以我们实际上是指 所有这些算法
作为n的顺序上 立方或大，O n立方的。
>> 下面是一些比较列表 常见的计算复杂性类
我们会遇到 算法，一般。
而在CS50还专门。
这些是从订购 通常最快在顶部，
到通常最慢的下方。
因此，固定的时间算法往往 是最快的，而不管
的大小的 数据输入你通过研究。
他们总是需要一个操作或 资源的一个单位来处理。
它可能是2，它可能 是3，它可能是4。
但这是一个常数。
它不改变。
>> 对数时间算法 是略胜一筹。
而一个真正的好例子 对数时间算法
你一定已经被看到现在是 撕裂电话簿
找到迈克·史密斯在电话簿。
我们切成两半的问题。
所以，当n变大 和更大和larger--
其实，每次增加一倍 N，只需要一个步骤。
所以这是好了很多 比说，线性时间。
这是你的两倍N，它 采取的步骤数量的两倍。
如果你三倍N，它需要 三倍的步骤的数量。
每单位的一个步骤。
>> 然后，事情变得有点缓慢 - 从那里少一点大。
你有线性的节奏，时而 所谓的对数线性时间或只是N日志ñ。
我们会为例 的算法的那
运行中的n log N，这仍然是更好的 比二次时间 - ñ平方。
或者多项式时间，n两个 任何数目大于2。
或指数的时间，这 甚至worse-- C到n个。
因此，一些常数提高到 输入的大小的功率。
所以，如果有1,000--如果 数据输入是大小1000，
它会采取C到第1,000权力。
这是一个很多比多项式时间差。
>> 阶乘时间更是雪上加霜。
而事实上，也确实 有无限的时间算法，
例如，所谓的愚蠢类别 - 其 工作是随机洗牌数组
然后检查 无论是排序。
如果它不是，随机 再次洗牌阵列
并检查是否它的排序。
正如你可能imagine-- 你能想象一个情况
其中在最坏的情况下，这种意愿 从来没有真正开始的数组。
该算法将永远运行。
因此，这将是一个 无限时间的算法。
希望你会不会写 任何因子或无限的时间
算法CS50。
>> 那么，让我们多了几分 具体看一些简单的
计算复杂性类。
因此，我们有一个example-- 两个例子这里 -
恒定时间算法， 它始终以
在最坏的情况下，单一的操作。
因此，第一个example-- 我们有一个函数
所谓的4对你来说，这 取大小1000的数组。
但后来显然 实际上不看
在它 - 并不真正关心什么 里面那个阵吧。
永远只是返回四个。
所以，这算法， 尽管事实上，它
需要1000元不 做他们什么。
刚刚返回四个。
它总是一个步骤。
>> 其实，加2 nums--这 我们以前作为well--见过
只是处理两个整数。
这不是一个单一的步骤。
它实际上是一对夫妇的步骤。
你得到了，你就会得到B，你加他们 在一起，你的输出结果。
因此，这84步。
但是，它总是不断的， 不管a或b。
你要得到一个，拿到B，加 在一起，输出其结果。
所以这是一个恒定的时间算法。
>> 这里有一个例子 线性时间算法 -
这gets--接受一个算法 一个附加步骤，可能的话，
作为输入增长了1。
因此，我们说，我们正在寻找 数5内的阵列。
你可能会遇到这样的情况 你可以找到它相当早。
但你也可以有 的情况下它
可能是该阵列的最后一个元素。
在大小5，数组，如果 我们正在寻找的数字5。
这将需要5个步骤。
而事实上，想象有 不随地5此数组中。
我们实际上仍然要看看 该阵列的每一个元素
为了确定 无论是否5是存在的。
>> 因此，在最坏情况下，这是 该元素是最后一个阵列中
或不存在的。
我们还是来看看 所有的n个元素。
因此该算法 以线性时间运行。
您可以确认通过 说外推一点点，
如果我们有一个6-元件阵列和 我们正在寻找5号，
它可能需要6个步骤。
如果我们有一个7-元件阵列和 我们正在寻找的数字5。
这可能需要7个步骤。
当我们增加一个元素，我们的 阵列，它需要一个步骤。
这是一个线性算法 在最坏的情况下。
>> 夫妇简单的问题给你。
什么是runtime--什么 最坏情况下的运行时
的代码，这个特殊的片段？
所以我有一个4环路这里运行 从第j等于0，一路为m。
而我所看到这里，是， 循环体运行在固定的时间。
因此，使用术语 我们已经谈过about--什么
将是最坏的情况 该算法的运行时间？
拿第二。
环路的内侧部分 运行在固定的时间。
和的外侧部分 回路将运行的m倍。
那么什么是最坏的情况下运行吗？
你猜大O m的？
你是对的。
>> 要不要再来一个？
这一次，我们有一个 环路的环路的内侧。
我们有一个外环 运行从零到第
我们有一个运行内环 从零到p和的里面，
予指出，人体的 环在固定时间内运行。
那么，什么是最坏情况下的运行时间 的代码，这个特殊的片段？
好了，再次，我们有一个 运行P乘以外环。
而且每个时间 - 迭代 该循环，而。
我们有一个内环 也运行P乘以。
然后那里面，还有的 恒时间 - 小片段存在。
>> 因此，如果我们有一个外循环 运行P乘以其内部是
内环那 运行p times--是什么
最坏情况下的运行时 这个代码片段？
你猜大O的P平方？
>> 我是道格·劳埃德。
这是CS50。