Хотя я понимаю, что большая запись O просто описывает скорость роста алгоритма, я не уверен, что есть какая-либо разница в эффективности в реальной жизни между следующими алгоритмами O (n).
Чтобы напечатать значение node в связанном списке k мест с конца списка.
Учитывая node:
/* Link list node */
struct node
{
int data;
struct node* next;
};
Решение 1 O (n)
Это решение выполняет итерацию по списку дважды, один раз, чтобы найти длину списка, и второй раз, чтобы перейти в конец списка - N.
void printNthFromLast(struct node* head, int n)
{
int len = 0, i;
struct node *temp = head;
// 1) Count the number of nodes in Linked List
while (temp != NULL)
{
temp = temp->next;
len++;
}
// Check if value of n is not more than length of the linked list
if (len < n)
return;
temp = head;
// 2) Get the (n-len+1)th node from the begining
for (i = 1; i < len-n+1; i++)
{
temp = temp->next;
}
printf ("%d", temp->data);
return;
}
Решение 2 O (n)
Это решение выполняет только итерацию по списку один раз. Указатель ref_ptr ведет, а второй указатель (main_ptr) следует за ним. Когда ref_ptr достигнет конца списка, main_ptr должен указывать на правильный node (k мест из конца списка).
void printNthFromLast(struct node *head, int n)
{
struct node *main_ptr = head;
struct node *ref_ptr = head;
int count = 0;
if(head != NULL)
{
while( count < n )
{
if(ref_ptr == NULL)
{
return;
}
ref_ptr = ref_ptr->next;
count++;
}
while(ref_ptr != NULL)
{
main_ptr = main_ptr->next;
ref_ptr = ref_ptr->next;
}
}
}
Вопрос: Несмотря на то, что оба решения O (n) в то же время оставляют значительную нотацию O, является ли второе решение более эффективным, чем первый для очень длинного списка, поскольку он только итерации над списком один раз?
