2024-09-27 18:01:45 发布
网友
任务:
given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
我的代码:
def search(A): j=1 while j in A: j+=1; return j;
为什么我的时间复杂性是O(N^2)?你知道吗
假设您的输入格式为1..N
然后,代码将执行N次迭代,每次迭代都可能检查列表的整个长度,以查看j的当前值是否在列表中。N检查长度N的整个列表的迭代得到N*N=N^2。你知道吗
这是一个最坏的例子,但是我们不知道典型的输入应该是什么。也许你知道,也许你不知道。一个简单且最坏的最佳方法是对列表进行排序,然后找出列表中项目之间的第一个“间隔”。像这样:
def my_search(A): A = [i for i in sorted(A) if i > 0] # Gets rid of <1 values as well min_pos_val = 1 for val in A: if val > min_pos_val: return min_pos_val min_pos_val += 1 return min_pos_val
“in”运算符是O(N)。 while是O(返回值)。你知道吗
[编辑]让我详细说明一下:您的代码相当于
j = 1 while True: # is O(the returned j) if j in A: # is O(N), bec. has to go through the whole array j += 1 else: return j
所以在最坏的情况下,你的算法确实是O(N^2)。在最佳情况下(例如,如果1不在A中),算法仅为O(N)。你知道吗
如果A是集合(不是列表或数组.array),平均为O(N)。 请参见此处的详细信息:https://wiki.python.org/moin/TimeComplexity或Complexity of *in* operator in Python。你知道吗
您正在对列表中所有肯定的项进行O(N)遍历。 在每一次迭代中,您都会让python通过询问“j in A”,在列表中进行另一次O(N)遍历?它可能遍历A的所有元素,搜索j。 所以你的复杂性变成:O(N) * O(N) = O(N^2)
O(N)
j in A
A
j
O(N) * O(N) = O(N^2)
假设您的输入格式为1..N
然后,代码将执行N次迭代,每次迭代都可能检查列表的整个长度,以查看j的当前值是否在列表中。N检查长度N的整个列表的迭代得到N*N=N^2。你知道吗
这是一个最坏的例子,但是我们不知道典型的输入应该是什么。也许你知道,也许你不知道。一个简单且最坏的最佳方法是对列表进行排序,然后找出列表中项目之间的第一个“间隔”。像这样:
“in”运算符是O(N)。 while是O(返回值)。你知道吗
[编辑]让我详细说明一下:您的代码相当于
所以在最坏的情况下,你的算法确实是O(N^2)。在最佳情况下(例如,如果1不在A中),算法仅为O(N)。你知道吗
如果A是集合(不是列表或数组.array),平均为O(N)。 请参见此处的详细信息:https://wiki.python.org/moin/TimeComplexity或Complexity of *in* operator in Python。你知道吗
您正在对列表中所有肯定的项进行
O(N)
遍历。 在每一次迭代中,您都会让python通过询问“j in A
”,在列表中进行另一次O(N)
遍历?它可能遍历A
的所有元素,搜索j
。 所以你的复杂性变成:O(N) * O(N) = O(N^2)
相关问题 更多 >
编程相关推荐