所有的权利,所以,计算复杂度。 只是有点警告 在我们深入太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。