为什么这个算法的运行时间是 O(m+n)?
Why is the runtime of this algorithm O(m+n)?
我不明白下面算法的运行时间怎么可以是O(m+n)。
关于算法,用于查找两个列表的公共节点(两个列表的长度可以不同)。
if (len1 < len2)
{
head1 = list2;
head2 = list1;
diff = len2 - len1;
}
这应该是 O(1)。
for(int i = 0; i < diff; i++)
head1 = head1->next;
O(n).
while(head1 != NULL && head2 != NULL)
{
if(head1 == head2)
return head1->data;
head1= head1->next;
head2= head2->next;
}
O(n).
我总共达到了 O(n^2)...
这里是完整的算法:
struct node* findMergeNode(struct node* list1, struct node* list2)
{
int len1, len2, diff;
struct node* head1 = list1;
struct node* head2 = list2;
len1 = getlength(head1);
len2 = getlength(head2);
diff = len1 - len2;
if (len1 < len2)
{
head1 = list2;
head2 = list1;
diff = len2 - len1;
}
for(int i = 0; i < diff; i++)
head1 = head1->next;
while(head1 != NULL && head2 != NULL)
{
if(head1 == head2)
return head1->data;
head1= head1->next;
head2= head2->next;
}
return NULL;
}
您所做的只是相互独立地迭代给定的列表。
实际上,这里花费时间最长的是确定列表的大小。 (仅此一项,如果 O(n+m)
)
struct node* findMergeNode(struct node* list1, struct node* list2)
{
// Assuming list1 is of size m
// Assuming list2 is of size n
int len1, len2, diff;
struct node* head1 = list1;
struct node* head2 = list2;
len1 = getlength(head1); // O(m) - as you need to iterate though it
len2 = getlength(head2); // O(n) - same here
diff = len1 - len2;
// Right now you already reached O(m+n)
if (len1 < len2) // O(1)
{
// this entire block is of constant length, as there are no loops or anything
head1 = list2;
head2 = list1;
diff = len2 - len1;
}
// So we are still at O(m+n)
for(int i = 0; i < diff; i++) // O(abs(m-n)) = O(diff)
head1 = head1->next;
// As diff = abs(m-n) which is smaller than m and n, we can 'ignore' this as well
// So we are - again - still at O(m+n)
while(head1 != NULL && head2 != NULL) // O(n-diff) or O(m-diff) - depending on the previous if-statement
{
// all the operations in here are of constant time as well
// however, as we loop thorugh them, the time is as stated above
if(head1 == head2)
return head1->data;
head1= head1->next;
head2= head2->next;
}
// But here again: n-diff < n+m and m-diff < n+m
// So we sill keep O(m+n)
return NULL;
}
希望这对您有所帮助。
我不明白下面算法的运行时间怎么可以是O(m+n)。 关于算法,用于查找两个列表的公共节点(两个列表的长度可以不同)。
if (len1 < len2)
{
head1 = list2;
head2 = list1;
diff = len2 - len1;
}
这应该是 O(1)。
for(int i = 0; i < diff; i++)
head1 = head1->next;
O(n).
while(head1 != NULL && head2 != NULL)
{
if(head1 == head2)
return head1->data;
head1= head1->next;
head2= head2->next;
}
O(n).
我总共达到了 O(n^2)...
这里是完整的算法:
struct node* findMergeNode(struct node* list1, struct node* list2)
{
int len1, len2, diff;
struct node* head1 = list1;
struct node* head2 = list2;
len1 = getlength(head1);
len2 = getlength(head2);
diff = len1 - len2;
if (len1 < len2)
{
head1 = list2;
head2 = list1;
diff = len2 - len1;
}
for(int i = 0; i < diff; i++)
head1 = head1->next;
while(head1 != NULL && head2 != NULL)
{
if(head1 == head2)
return head1->data;
head1= head1->next;
head2= head2->next;
}
return NULL;
}
您所做的只是相互独立地迭代给定的列表。
实际上,这里花费时间最长的是确定列表的大小。 (仅此一项,如果 O(n+m)
)
struct node* findMergeNode(struct node* list1, struct node* list2)
{
// Assuming list1 is of size m
// Assuming list2 is of size n
int len1, len2, diff;
struct node* head1 = list1;
struct node* head2 = list2;
len1 = getlength(head1); // O(m) - as you need to iterate though it
len2 = getlength(head2); // O(n) - same here
diff = len1 - len2;
// Right now you already reached O(m+n)
if (len1 < len2) // O(1)
{
// this entire block is of constant length, as there are no loops or anything
head1 = list2;
head2 = list1;
diff = len2 - len1;
}
// So we are still at O(m+n)
for(int i = 0; i < diff; i++) // O(abs(m-n)) = O(diff)
head1 = head1->next;
// As diff = abs(m-n) which is smaller than m and n, we can 'ignore' this as well
// So we are - again - still at O(m+n)
while(head1 != NULL && head2 != NULL) // O(n-diff) or O(m-diff) - depending on the previous if-statement
{
// all the operations in here are of constant time as well
// however, as we loop thorugh them, the time is as stated above
if(head1 == head2)
return head1->data;
head1= head1->next;
head2= head2->next;
}
// But here again: n-diff < n+m and m-diff < n+m
// So we sill keep O(m+n)
return NULL;
}
希望这对您有所帮助。