srcmini本文概述
算法的复杂度是算法对于给定大小(n)的输入所需要的时间和/或空间量的度量。虽然算法的复杂度确实取决于特定因素, 例如：计算机的体系结构, 即抽象数据类型(ADT)编译器的硬件平台表示, 可以有效提高输入的基础算法大小的复杂度。尽管你会看到最重要的因素是底层算法的复杂性和输入的大小。
在srcmini的博客” Python数据结构教程”中, 你可以在该博客中了解数据结构的基本概述以及Python中数据结构的实现。该博客文章介绍了Python的基本数据结构。有了它, 你将发现抽象数据类型和数据结构, 原始数据结构和非原始数据结构。
渐近分析
渐近分析是指以计算的数学单位来计算任何代码的运行时间或运算。它的运算是根据像f(n)这样的函数来计算的。在数学分析中, 渐近分析(也称为渐近分析)是一种描述极限行为的方法。
算法所需的时间分为以下三种类型：最坏情况-算法所需的最大时间, 在分析算法时通常会使用或完成。最佳情况-算法或一段代码所需的最短时间, 通常在分析算法时不会计算出来。平均用例-算法或部分代码所需的平均时间, 有时需要在分析算法时完成。
渐近符号
计算算法运行时间复杂度的常用符号如下：
- 大O符号
- 大θ符号
- 大Ω表示法
大O记法, Ο
Big O用于衡量算法的性能或复杂性。用更数学的术语来说, 它是函数增长率的上限, 或者如果函数g(x)的增长不快于函数f(x)的速度, 则称g是O(f )。通常, 它用于表示算法的上限, 它给出了算法可能花费的最慢时间复杂度或最长时间来度量的度量。
大Ω符号, Ω
Ω(n)表示形式是算法运行时间的下限。它测量最佳情况下的时间复杂度或算法可能花费的最佳时间。
大θ表示法, θ
θ(n)表示形式是算法运行时间的下限和上限。
表示法用于确定各种算法的复杂度
大O表示法是最常用的, 并且主要用于查找算法的上限, 而有时使用Bigθ表示法来检测平均情况, 而Ω表示法是使用最少的表示法。三。
你将看到算法中用于确定特定算法复杂性的符号示例。
例如, 快速排序：
快速排序是一种分而治之算法, 用于排序。它用作按顺序排列元素的系统方法, 例如, 按数组的升序或降序排列元素或数字。该算法选择从给定数组中选择的枢轴或索引。同样, 可以以不同方式选择枢轴。下面实现的示例是使用最后一个元素选择的数据透视元素。
快速排序的主要要点是分区。从一个数组中, 选择一个分隔元素, 然后将分隔元素(例如, pit)保持在正确的位置, 然后将大于分隔元素的元素保留在凹坑的右侧, 将较小的元素保留在坑的左边。
#The last element will be taken as a pivot by the use of the function
#The smaller element is placed left to the pivot
#The greater element is placed to the right of the pivot
def partition(array, low, high):
i = ( low-1 ) # index of smaller element is chosen
pivot = array[high] # pivot is chosen
for j in range(low , high):
#Is the element less or equal to the pivot
if array[j] <= pivot:
# increment index of smaller element
i = i+1
array[i], array[j] = array[j], array[i]
array[i+1], array[high] = array[high], array[i+1]
return ( i+1 )
# The main crux of the problem that implements Quick sort is
#array[] is to be sorted
#high is the ending index
#low is the starting index
# Function to do Quick sort
def quickSort(array, low, high):
if low < high:
#pit is the partitioning index
pit = partition(array, low, high)
#Element sorted before and after partition
quickSort(array, low, pit-1)
quickSort(array, pit+1, high)
array=[2, 4, 6, 8, 10, 12]
n = len(array)
quickSort(array, 0, n-1)
print ("The Sorted array is:")
for i in range(n):
print ("%d" %array[i]), Sorted数组为：
2
4
6
8
10
12
你将获得输出：
排序数组为：2 4 6 8 10 12
现在该分析时间复杂度了。首先,
- 最好的情况是：Ω(n log(n))
- 平均情况为：Θ(n log(n))
- 最坏的情况是：O(n ^ 2)
现在, 让我们分析上面的代码。
最佳情况：分区元素选择中间元素作为枢轴的情况是这样, 即由于算法将在上半部分和下半部分递归调用。因此-所需的步骤总数是将问题每步除以2所需的次数, 即从n变为1。因此, 有n / 2/2/2/2 /…./ 2 = 1 * k次但是, 请注意, 等式实际上是：n / 2 ^ k =1。由于2 ^ logn = n, 我们得到k = long。因此, 算法所需的步骤(迭代)数为O(log), 这将使算法为O(n log n)-因为每次迭代均为O(n)。
平均情况：要进行平均情况, 我们需要考虑数组的所有排列并计算每个排列所花费的时间。你可以在合并排序中更多地参考它。
最坏的情况：在最坏的情况下, 如果选择第一个元素作为枢轴, 则当要排序的输入按升序或降序排序时, 将选择最坏的情况。最坏情况的原因是在分区之后, 分区大小将为1, 其他大小将为n-1。在这里, T(n)是函数：因此, 对n个元素进行快速排序的时间T(n)=对n个元素进行分区所需的时间O(n)+对n-1个元素进行快速排序的时间T(n-1)因此, T(n)= T(n-1)+ O(n)=> T(n)= O(n ^ 2)
例子
下面的代码可能并不是那么花哨, 你可能不会将其称为算法, 但是你可以将其视为算法, 因为任何从根本上说什么都不做的代码都是算法, 并且是解决特定问题的一种方式。你可以在上面看到的算法是使用包含单个print语句的for循环。
print('I love Python');
你好, 世界！
上述算法的时间复杂度为O(1), 因为它总是需要一步。这是一个恒定的时间。
stuffs= ['eggs', 'toothbrush', 'kittens', 'mugs']
for stuff in stuffs:
print("Here's a stuff: {}".format(stuff));
这是一个东西：鸡蛋这是一个东西：牙刷这是一个东西：小猫这是一个东西：杯子你如何用Big O表示法描述上述算法的效率？
为了分析上述算法, 你需要考虑一个事实或分析该算法需要执行多少步骤。在上述情况下, 它在列表中有四个项目, 你需要一次打印一次。但是现在你要考虑并考虑, 如果列表中的元素或项目多于4个, 即说比for循环多15个项目, 那么对于列表中的15个项目也将采取相同的步骤数呢？由于此for循环采取与元素一样多的步骤, 因此你需要说该算法的效率为O(N)而不是O(1)。
下一个示例是一个简单的基于Python的算法, 用于确定数字是否为质数：
def is_prime(number):
for i in range(2, number):
if number % 2 == 0:
return True
return False
前面的代码接受一个数字作为参数, 并开始for循环, 在该循环中, 你将每个数字从2除以该数字, 然后看是否还有余数。如果没有余数, 你就会知道该数字不是素数, 并立即返回False。如果你一直使用数字, 并且总是找到余数, 那么你就知道该数字是质数, 并且返回True。
你可以将上述算法的效率确定为O(N)。上面的示例未采用数组或列表形式的数据, 但传入的数字作为参数。如果传递任意数字(例如11), 则for循环将运行约11个步骤。 (实际上它运行9步, 因为它从2开始并在实际数字之前结束。)对于数字101, 循环运行约101步。由于步数随着传递到函数中的步数而逐步增加, 因此这是O(N)的经典示例。
def twoForLoops(n):
for i in range(1, n):
print("Printing:"+i);
for i in range(1, 100):
print("Printing:"+i);
在上面的代码中, 算法的复杂度为O(N), 因为第二个循环确实包含100作为参数, 可以忽略, 因为你需要通过假设N非常大来表示复杂度。
def twoConditionalLoops(m, n):
for i in range(0, m):
print("Printing:"+i);
for i in range(0, n):
print("Printing:"+i);
有两个循环, 其中一个循环的长度为m, 另一个循环的长度为n。另外, 你需要假定m和n较大, 然后运算的复杂度为O(n + m)。由于回路不同并且需要不同的输入, 因此复杂性本质上是累加的。
def twoNestedForLoops(int m, int n):
for i in range(0, n):
for j in range(0, m):
print("Printing:"+(i*j));
有一个嵌套的for循环, 再次需要假设n和m较大, 然后运算的复杂度为O(n * m)。由于循环是相同的并且是嵌套的, 因此复杂度本质上是乘法的。
恭喜！
你已经完成了本教程的结尾！在此过程中, 你学习了渐近符号以及程序员和数据科学家使用的基本工具。你已经学到了一种简单而复杂的分析复杂性的方法, 该方法仅使用简单的英语编写, 没有给出专业的词汇和数学上的严谨性。尽管仅当你是计算机科学专业的本科生或相关领域的人才会阅读和教授数据结构和算法主题。拥有有关此主题的知识(即不是专家)同样重要。要深入了解学习过程, 可以参考此链接。 MIT开放式课件算法课程
如果你想了解有关Python的更多信息, 请查看以下srcmini课程：
- 卷积神经网络的图像处理
- Python中的统计模拟
评论前必须登录！
注册