從我寫了這個程序從一個未排序的鏈表中刪除重複的節點鏈表

Question

刪除重複的理解複雜：

#include<bits/stdc++.h> 
using namespace std; 

/* A linked list node */ 
struct Node 
{ 
    int data; 
    struct Node *next; 
}; 

// Utility function to create a new Node 
struct Node *newNode(int data) 
{ 
    Node *temp = new Node; 
    temp->data = data; 
    temp->next = NULL; 
    return temp; 
} 

/* Function to remove duplicates from a 
    unsorted linked list */ 
void removeDuplicates(struct Node *start) 
{ 
    // Hash to store seen values 
    unordered_set<int> seen; 

    /* Pick elements one by one */ 
    struct Node *curr = start; 
    struct Node *prev = NULL; 
    while (curr != NULL) 
    { 
     // If current value is seen before 
     if (seen.find(curr->data) != seen.end()) 
     { 
      prev->next = curr->next; 
      delete (curr); 
     } 
     else 
     { 
      seen.insert(curr->data); 
      prev = curr; 
     } 
     curr = prev->next; 
    } 
} 

/* Function to print nodes in a given linked list */ 
void printList(struct Node *node) 
{ 
    while (node != NULL) 
    { 
     printf("%d ", node->data); 
     node = node->next; 
    } 
} 

/* Driver program to test above function */ 
int main() 
{ 
    /* The constructed linked list is: 
    10->12->11->11->12->11->10*/ 
    struct Node *start = newNode(10); 
    start->next = newNode(12); 
    start->next->next = newNode(11); 
    start->next->next->next = newNode(11); 
    start->next->next->next->next = newNode(12); 
    start->next->next->next->next->next = 
            newNode(11); 
    start->next->next->next->next->next->next = 
            newNode(10); 

    printf("Linked list before removing duplicates : \n"); 
    printList(start); 

    removeDuplicates(start); 

    printf("\nLinked list after removing duplicates : \n"); 
    printList(start); 

    return 0; 
} 

是否找到每個元素在哈希表影響的複雜性？如果是，那麼考慮到該集合被實現爲二進制搜索樹，該算法的時間複雜度應該是多少，其中在最壞情況下搜索元素的成本是O（logn）。根據T（n）= T（n-1）+ log（n-1）即，第n個元素將執行log（n-1）比較（即具有n-1個元素的樹的高度） 請給出數學分析。

Answer 1

查找散列表中的每個元素是否會影響複雜性？

那麼，在你的代碼中使用unordered_set這爲O的平均複雜性（1），所以簡單的答案是 -

號......考慮到集爲實現在最壞的情況下搜索元素的代價是O（logn）的二元搜索樹。

再次，您選擇了unordered_set這不是二進制搜索。我相信一些set的實現使用紅色/黑色樹，你會看O（logN），但是與unordered_set它應該是恆定的時間。所以現在唯一的問題是遍歷鏈表。其中，由於您只是在訪問每個節點時朝一個方向行走，因此是O（N）操作。