在解决编码方面的问题时,我们经常提出一种算法,这是解决问题的一组指令。为了让您了解算法,请想象您有很多未分类的数字,并且您想找到其中最大的数字。这是一种直接解决此问题的简单算法:
- 从列表中的第一个数字开始,并将其称为“当前最大数字”。
- 将“当前最大数字”与列表中的下一个数字进行比较。
- 如果下一个数字大于“当前最大数字”,则将“当前最大数字”更新为下一个数字。
- 移至列表中的下一个数字,然后重复步骤2和3,直到您比较了所有数字。
- 最后,“当前最大数字”将是列表中最大的数字。
那里有!一种简单的算法来解决问题。某些算法比其他算法更快,更高效,尤其是在处理大量数据时。这样考虑:考虑有两种方法来安排一堆论文。一种方法是单独检查每篇论文,对其进行比较,然后对其进行重新排列,直到它们的顺序正确为止。替代过程需要将桩切成两半,独立对每个一半进行排序,然后将它们结合在一起。您认为随着堆越来越大,哪种方法会更快地进行?我们可以使用大o符号来回答这样的问题。它使我们能够评估算法的资源或时间要求如何随输入的大小而变化。您可以通过对大o符号有牢固的了解来为各种任务选择正确的算法。
什么是大O?
big o是一种测量算法效率或运行速度的效率,它有助于我们了解算法的性能如何随着其处理数据的增长而变化。
通常,面试官会问有关大o的问题,或要求您编写代码,然后评估代码的速度或高效。
时间复杂性与空间复杂性
假设您有秒表,并且已经编写了两个代码,代码A和代码B。如果您运行代码A并启动秒表,并且需要20秒才能运行代码A,则可以重置秒表,然后运行代码b,代码B运行花了40秒钟,基于此,您会说代码A的运行速度比代码B快,您可以测量它,这称为 time复杂性。关于时间复杂性的一个非常有趣但令人困惑的事情是,它不是在及时衡量的,而是在完成任务时需要进行的操作数量。想象一下,您将代码B(从上面的示例中)运行,并在计算机上运行它的处理器三次,它将在代码A之前完成,但这并不意味着代码B更快或更有效,它只是意味着计算机是更好的是,我们使用操作数量而不是时间来评估时间复杂性。
空间复杂性另一方面是指算法所需的记忆或存储空间的数量来解决问题。它衡量算法的内存使用方式如何随输入的大小而变化。
为什么空间复杂性也很重要?我们在编写代码时大多优先考虑速度,但是为什么我们也需要考虑空间复杂性呢?
同样,从代码A和代码B之间的比较,可以说,当代码A运行速度时,它需要更多的内存空间,但是代码B即使运行较慢,代码B也需要更少的内存空间。在某些情况下,需要考虑内存空间,因此在编写代码时也要考虑空间复杂性很重要。
Big O(O),Omega(©)和Theta(歧)
这些是时间和空间复杂性中常用的表示法,它们表示以下内容:
big o(o):大o符号代表算法时间或空间复杂性的上限或最坏情况。
Omega(©):欧米茄符号表示算法的时间或空间复杂性的下限或最佳场景。
theta(_): theta符号表示算法的时间或空间复杂性的上限和下限。
我想想这些符号的方式是七个项目的列表,我写了一个for loop,以迭代这些项目以找到特定的项目。
假设您正在寻找数字1,那是您最好的场景(Omega(©)),因为您将仅在一个操作中获得列表中的第一项,但是如果您想获得数字,则7 ,这是您最糟糕的场景(O),因为7是列表中的最后一项,您必须仔细阅读整个列表才能浏览它。要获得第4名,这就是您的平均案例(theta(歧)),因为它在您的最佳案例和最差案例之间。
常见时间复杂性
在):
这是最简单的理解。考虑要在篮子里计算橙子的任务。假设您算出一个一个橙子,一个一个一个一个。您需要10个单位或精力来完成工作。现在,如果您有20个橘子而不是10个橙子,则大约需要您两倍的工作时间才能计算它们。
o(n),其中“ n”代表输入大小,是这种线性关系的数学表示。它表明,完成活动所需的时间或精力以与输入大小相同的速度(橙色数)上升。如果您有两倍的橙色,则花费的时间或精力大约是两倍。
一个简单的代码示例:
def print_items(n):
for i in range(n):
print(i)
print_items(5)
输出:
0
1
2
3
4
代码打印了五(5)个项目,因为我们通过了参数n = 5,因此需要5个单位的努力才能完成任务,因此无论n是什么,这都是操作的数量。这意味着完成算法或操作所需的时间随输入的大小而线性增加。
让我们看一下O(n)的图:
o(n^2):
简单地说,o(n^2)表示算法的时间或空间复杂性随输入大小而倍增。为了用代码说明这一点,让我们在另一个循环中写一个“ for loop'for Loop'
def print_items(n):
for i in range(n):
for j in range(n):
print(i,j)
print_items(5)
输出:
0 0
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 2
4 3
4 4
因此,从0,0到4,4,我们打印了25个项目,输入尺寸n = 5,但我们得到了25个打印的n * n = n^2项目,因此却没有跨越二次关系。 ``for循环''内部'for loop'这是o(n^2)的一个很好的例子
图:
0(1):
o(1)意味着算法的时间或空间复杂性保持不变,无论输入大小如何。这种恒定关系由O(1)表示,也称为“恒定时间复杂性”。这意味着执行任务所需的时间或精力保持不变,无论输入大小如何。相同数字的添加就是一个例子:
def add_num(n):
return n + n
add_num(1)
add_num(2000)
输出:
2
4000
随着输入尺寸的增加,我们已经看到的其他操作也增加了,但操作的数量也会增加,但是这种恒定的时间复杂性是不同的。即使n = 100000000,也只有一个操作即可完成,即n + n = 100000000 + 100000000 = 200000000,即o(1),即恒定时间。
在图上:
o(1)由图表上的水平蓝线表示,这是最有效的大o,只要您可以将代码优化到o(1),这是最有效的,您可以拥有它。<<<<<<<<<<<<<<< /p>
o(logn)
o(log n)表明算法的时间或空间复杂性随着输入量的增加而对数增加。
让我们以词典中查找单词的示例来进一步理解这一点。您可以使用更有效的策略,而不是从第一页开始并逐一翻阅每个页面。您可能会大致在中间打开字典,并检查您要寻找的单词是否在该页面之前或之后。根据结果,您可以消除剩余页面的一半并重复该过程。您可以通过反复“半”搜索区域轻松地进入该位置。
o(log n),其中“ n”是输入大小,代表这种对数关系。这意味着随着输入的规模的扩大,任务的时间或精力要求不断增加,但不会按比例地增加。另外,它可以对数上升。让我们在Python中写一个传统的二进制搜索
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2 # Find the middle index
if arr[mid] == target: # if the the middle element is the target
return mid
elif arr[mid] < target: # If the target is greater, search the right half
low = mid + 1
else: # If the target is smaller, search the left half
high = mid - 1
return -1 # Target not found
# Example usage
arr = [2, 5, 7, 12, 16, 21, 28, 36]
target = 16
result = binary_search(arr, target)
if result != -1:
print("Target found at index", result)
else:
print("Target not found")
此代码中的binary_search函数在排序列表上运行一个O(log n) - 时间复杂的二进制搜索。搜索空间反复分为一半,直到目标元素的定位或搜索空间用完为止。
该函数的输入参数是数组(ARR)和目标值(目标)。初始化了两个低和高的指针,以保持搜索范围的跟踪。它决定了中间索引(中间),并将中间元素与段循环内的所需值进行比较。它根据比较更新低和高搜索参数。如果找到目标,它将返回索引;否则,它给出-1以证明目标不在数组中。
二进制搜索算法表现出O(log n)时间复杂性属性,因为迭代的数量随着列表的大小增加而对数增长。
结论
即使您没有准备面试,但您有兴趣制定有效的代码,学习大o符号也非常有帮助。大符号使您能够理解算法效率,做出更明智的软件开发决策并与其他开发人员进行互动。它是提高性能和开发更有效的软件的有用工具。
我发表了一篇文章,详细介绍了我如何使用Python解决Leetcode挑战“两个总和”。我想出了两种方法,第一种方法是我的第一个策略。我只是有兴趣使代码运行。我不在乎它占用了多少空间或运行的速度。通过使用对Big O的理解,我能够创建第二种,更有效的方法。本文可以在这里访问。 Two Sum - LeetCode problem 1 solution in python
在Twitter @Sammie_savvie上对我打招呼