算法：大O符号解释

O（n），O（1），O（log n）等大O符号被用来表示算法的效率。在这篇文章中，你会找到每个大O符号的例子和解释。

本文旨在解释大O符号是简单的。大多数学生和程序员都理解O（n）和O（1），但是理解O（log n）却有点困难。我尽可能简单地解释三个基本的大O符号。

让我们来回顾一下。

什么是算法？

算法是用来完成特定操作或解决问题的方法。我们都知道，解决某个问题的方法不止一种，同样，可以用多个算法来解决一个给定的问题。

想象一个场景：如果有多个算法/步骤来解决问题，我们如何找到哪个更好或更有效？

为了表示算法的效率，使用O（n），O（1），O（log n）等大O符号。

常见的大O符号是：

• O（n）：线性时间操作。
• O（1）：恒定时间操作。
• O（log n）：对数时间操作。

为了理解大O符号，我们需要了解恒定时间操作，线性时间操作和对数时间操作。

现在让我们一起来随着例子/问题来学习这些大O符号。

O（n）：线性时间操作

需要解决的问题：假设我们有一个包含数字或卡片的盒子（如1,2,3,4，... 16），我们被问到盒子里是否有数字6。我们需要做什么？

每次选择一个号码，并检查我们选择的号码是6（搜索的号码）。

如果我们挑选的号码与搜索的号码相符，那就很好。否则，我们需要从框中选择另一个号码。这种一次挑选一个数字并验证它是否一个接一个地匹配直到所有n个数字都被挑选出来的方法称为线性运算。这种搜索n个数字的方式表示为O（n）。如果找到的号码是最后一个号码（最坏的情况），我们就需要将这n个数字都挑选一遍。。

int n = 16;

int[] numbers = {11,12,13,14,15,16,1,2,3,4,5,6,7,8,9,10};

int numberToSearch = 16;

int find(int numberToSearch, int[] numbers) {

for (int i = 0; i < n; i++) {

    if (numbers[i] = numberToSearch)

        return i; //FOUND

}

return -1; //NOT FOUND

}

O（1）：恒定时间操作

亟待解决的问题：假设我们得到一盒数字（1,2,3,4，... 16），并且在盒子外面印有“盒子包含16个数字”。你会被问到盒子里有多少个数字/项目。因为你知道这个盒子被标记为包含16个球，所以你回复说这个盒子包含了16个。如果另一个人第二天问你同样的问题，你可以通过查看盒子再次回答，即使你得到另一个盒子100数字，如果它有一个标签说，该盒子包含100个数字，你依旧可以通过查看盒子再次回答。这被称为恒定时间操作。它表示为O（1）。

int n = 16;

int[] numbers = {11,12,13,14,15,16,1,2,3,4,5,6,7,8,9,10};

int findSize(int[] numbers) {

     return numbers.length;

}

O（log n）：对数时间操作

需要解决的问题：假设我们有一个包含数字（1，2，3，4，... 16）的框，并且所有的数字都是有序的。你被要求在框中找到一个数字16。这里的问题是数字是有序的。我们把这些数字分成两部分。这16个数字被分成两组，每组包含8个。

int n = 16;

int[] numbers = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};

int numberToSearch = 16;

int median = 16/2 = 8;

int[] split1 = {1,2,3,4,5,6,7,8};

int[] split2 = {9,10,11,12,13,14,15,16}

数字16大于分组中的最大元素，因此要搜索的数字将仅被一分为二继续寻找，分割将会一直继续直到数字的末尾或找到了待搜索的数字。

因此：

看上面的图片，我们可以在4个步骤中找到一个数字（在16个数字的列表中）。

这可以写成，

在数学中，如果n = 2x，则log2 n = x。 （请参考二进制对数）

因此16 = 24可以写成log2 16 = 4。

这可以写成log2 n，或简单地写成O（log n）。

因此，需要四个步骤来找到一个包含16个数字的盒子，每个步骤将盒子分成两部分（这也称为二分查找）。

int find(int[] numbers, int numberToSearch) {

        int left = 0;

        int right = numbers.length - 1;

       while (left <= right) {

          int mid = left + (right - left) / 2;

          if (numberToSearch < numbers[mid]){

              right = mid - 1;

          }

          else if (numberToSearch > numbers[mid]) { 

              left = mid + 1;

          }

          else {

              return mid; //NUMBER FOUND

          }

        }

        return -1; //NUMBER NOT FOUND

 }

我希望这很简单，或者至少容易理解！

另一个例子：

例如，如果我们有64个数字，那么找到一个数字的最大步数可以如下推导出来，

64 = 26（2的6次方），这可以写成log2 64 = 6。因此，最多需要6个步骤才能在64个数字列表中找到一个数字。