虽然我们将常量放在大O符号中,但它在现实生活中是否重要？

虽然我知道大O符号只是简单地描述了算法的增长率,但我不确定以下O(n)算法之间在现实生活中的效率是否有任何差异.

从列表末尾打印链接列表中的节点值.

给定一个节点:

/* 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应指向正确的节点(列表末尾的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表示法放在一边,第二个解决方案是否比第一个解决方案更有效,因为它只迭代列表一次？

1> Fantastic Mr..：

---

是.在发生相同工作的特定示例中,单个循环可能比循环两组数据更有效.但O(2n)〜的想法O(n)是2 ns vs 1 ns可能并不重要.大O工作更好地表明,如果你做的循环一段代码可能会扩展,如O(n^2)再之差O(n)VS O(2n)远小于O(n)VS O(n^2).

如果您的链表包含数TB的数据,则可能值得减少到单循环迭代.在这种情况下,一个大的O指标可能不足以描述您的最坏情况; 你最好定时代码并考虑应用程序的需求.

另一个例子是嵌入式软件,其中1 ms vs 2 ms可能是500 Hz和1 kHz控制环之间的差异.

吸取的教训是它取决于应用程序.

---

@Johntarmac:还是有*渐近*.O(2N)= O(N),它们是完全相同的类别,没有任何差异.就像O(1)= O(2),或O(N ^ 2)= O(50N ^ 2 + 100N + 99999999 log N).

2> Mark Ransom..：

---

只有顺序相同且常规操作具有可比性,该常量才有意义.如果它们的顺序不同,那么具有较高顺序的顺序一旦足够大,就可以保证更长的顺序n.有时n必须大于典型数据集,选择最有效算法的唯一方法是对它们进行基准测试.