预告片

算法:解决问题的程序/公式

---

如何分析算法,如何比较算法?

例如:你和一个朋友被要求创建一个函数,将数字从 0 到 N. 你与 f(x) 和你的朋友与 g(x) 相同的结果,但两个函数有不同的算法。

Big-O 评分:描述运行时间将与输入相对增长的速度,因为输入随意大。

三个关键点:

比较运行时间的增长速度 不要比较准确的运行时间(取决于硬件) 只关心运行时间的增长与输入(n) 因为n 随意大,专注于将增长最快的术语,因为n 得到大(想想无限) AKA 无形分析

空间复杂性:除了时间复杂性之外,我们也关心空间复杂性(一个算法使用的内存/空间多少)。

EDIT:快注,这几乎是令人困惑的Big O评分(这是一个上线)与Theta评分(这是一个上线和下线)。在我的经验中,这实际上是非学术设置讨论的典型。

在一个句子中:随着你的工作的规模上升,完成工作需要多长时间?

“大O”评分的一个重要方面是,它不会说哪个算法会更快到一个特定的尺寸。 采取一个字符串(字符串,整体值)对一系列对(字符串,整体值)。 是否更快地找到字符串中的关键或字符串中的元素,基于字符串? (即字符串, “找到字符串部分与特定的关键相匹配的第一个元素” ) 字符串是基因。

大 O 在平式英语是如<=(少于或等)。当我们说为两个函数f 和 g,f = O(g) 它意味着f <= g。

但是,这并不意味着任何 n f(n) <= g(n) 事实上,它意味着 f 是增长方面低于或等于 g 的,这意味着在一个点 f(n) <= c*g(n) 之后,如果 c 是恒定的,然后一个点意味着所有 n >= n0 在那里 n0 是另一个恒定的。

“什么是明确的英语解释大O?尽可能少的正式定义和简单的数学。

这样一个美丽简单而短暂的问题似乎至少值得一个同样短暂的答案,就像一个学生在教学期间可以得到的那样。

大 O 评级简单地说明一个算法可以运行多长时间,仅仅是输入数据的数量。

(在一个美妙的,无单位的时间感中!)(这就是重要,因为人们总是想要更多,无论他们生活在今天还是明天)

好吧,什么是那么奇妙的关于大O评级,如果这就是它做什么?

实际上,Big O分析是如此有用和重要,因为Big O把重点放在算法本身的复杂性上,完全忽略了一切只是比例性恒定的东西 - 如JavaScript引擎,CPU的速度,您的互联网连接,以及所有快速变成像模型T一样可笑的过时的东西。

这里来了大O,告诉我们这个数学是多么艰难。

现在他们要求我添加一个到十个!为什么我会这样做?我不想添加一个到六个?添加一个到十个......好......这会更难!

对于大 n 而言, n 平方比 n 更大。

一个:我选择一张卡在我们现在工作的地板部分,你可以为我选择一个,如果你愿意(第一次我们这样做,“我们现在工作的地板部分”是整个地板,当然。

大 O 告诉我们:这个类型需要 O(n log n) 工作完成,在中间情况下。

现在你知道我的朋友,大O,他帮助我们做不到工作,如果你知道大O,你也可以做不到工作!

你和我一起学到了这一切!你太聪明了!谢谢你!

现在这个工作已经完成了,让我们玩吧!

---

Big-O 是由程序所消耗的资源增加率,即问题例大小。

资源:可能是CPU时间,可能是最大 RAM 空间。

说问题是“找到金额”,

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

problem-instance= {5,10,15} ==> problem-instance-size = 3, iterations-in-loop= 3

problem-instance= {5,10,15,20,25} ==> problem-instance-size = 5 iterations-in-loop = 5

说问题是“找到组合”,

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

problem-instance= {5,10,15} ==> problem-instance-size = 3, total-iterations = 3*3 = 9

problem-instance= {5,10,15,20,25} ==> problem-instance-size = 5, total-iterations= 5*5 = 25

对于“n”尺寸的输入,该程序以序列中的“n*n”节点的速度生长,因此,Big-O是N2以O(n2)表达。