1.介绍 在计算机科学中，算法的时间复杂度量化算法作为表示输入的字符串的长度的函数而运行的时间量。 2.大O符号 算法的时间复杂度通常用大O符号表示，不包括系数和低阶项。当用这种方式表示时，时间复杂度被认为是渐进地描述的，也就是说，随着输入大小变为无穷大。 例如，如果一个算法对所有n的输入所需的时间至多为5n 3 + 3n，则渐近时间复杂度为O（n 3）。稍后更多。 几个例子： 1 = O（n） n = O（n 2） log（n）= O（n） 2 n + 1 = O（n） 3. O（1）恒定时间： 如果算法需要相同的时间而不管输入大小如何，算法被认为是在恒定的时间内运行的。 例子： 数组：访问任何元素 固定大小的堆栈：推送和弹出方法 固定大小的队列：入队和出队方法 4. O（n）线性时间 如果算法的时间执行与输入大小成正比，则算法被称为以线性时间运行，即随着输入大小的增加，时间线性地增长。 考虑下面的例子，下面我直线地搜索一个元素，这有一个O（n）的时间复杂度。 int find = 66; var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 }; for (int i = 0; i < numbers.Length - 1; i++) { if(find == numbers[i]) { return; } } 更多示例： 数组：线性搜索，遍历，查找最小等 ArrayList：包含方法 队列：包含方法 5. O（log n）对数时间： 如果算法的时间执行与输入大小的对数成比例，则算法被称为在对数时间运行。 示例：二进制搜索 回想一下“二十问题”游戏 - 任务是在一个区间内猜测一个隐藏号码的值。每次猜测，你都会被告知你的猜测是太高还是太低。二十个问题的游戏意味着一个策略，使用你的猜测数量减半区间大小。这是解决二进制搜索的一般问题解决方法的一个例子 6. O（n2）二次时间 如果算法的时间执行与输入大小的平方成正比，则算法被称为以二次方式运行。 例子： 泡沫排序 选择排序 插入排序 7.一些有用的链接 大O的误解 确定算法的复杂性 大O备忘录1.介绍 在计算机科学中，算法的时间复杂度量化算法作为表示输入的字符串的长度的函数而运行的时间量。 2.大O符号 算法的时间复杂度通常用大O符号表示，不包括系数和低阶项。当用这种方式表示时，时间复杂度被认为是渐进地描述的，也就是说，随着输入大小变为无穷大。 例如，如果一个算法对所有n的输入所需的时间至多为5n 3 + 3n，则渐近时间复杂度为O（n 3）。稍后更多。 几个例子： 1 = O（n） n = O（n 2） log（n）= O（n） 2 n + 1 = O（n） 3. O（1）恒定时间： 如果算法需要相同的时间而不管输入大小如何，算法被认为是在恒定的时间内运行的。 例子： 数组：访问任何元素 固定大小的堆栈：推送和弹出方法 固定大小的队列：入队和出队方法 4. O（n）线性时间 如果算法的时间执行与输入大小成正比，则算法被称为以线性时间运行，即随着输入大小的增加，时间线性地增长。 考虑下面的例子，下面我直线地搜索一个元素，这有一个O（n）的时间复杂度。 int find = 66; var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 }; for (int i = 0; i < numbers.Length - 1; i++) { if(find == numbers[i]) { return; } } 更多示例： 数组：线性搜索，遍历，查找最小等 ArrayList：包含方法 队列：包含方法 5. O（log n）对数时间： 如果算法的时间执行与输入大小的对数成比例，则算法被称为在对数时间运行。 示例：二进制搜索 回想一下“二十问题”游戏 - 任务是在一个区间内猜测一个隐藏号码的值。每次猜测，你都会被告知你的猜测是太高还是太低。二十个问题的游戏意味着一个策略，使用你的猜测数量减半区间大小。这是解决二进制搜索的一般问题解决方法的一个例子 6. O（n2）二次时间 如果算法的时间执行与输入大小的平方成正比，则算法被称为以二次方式运行。 例子： 泡沫排序 选择排序 插入排序 7.一些有用的链接 大O的误解 确定算法的复杂性 大O备忘录... 展开详请