Вычислительная сложность программы

Question

я написал следующую программу, которая должна ответить на этот вопрос

Написать эффективную функцию, чтобы найти первый бесповторного символ в строку. Например, первый неповторяющийся символ в «total» равен 'o', а первый неповторяющийся символ в «teter» равен 'r'. Обсудите эффективность вашего алгоритма.

Это то, что я сделал:

#include <stdio.h> 
#include <iostream> 
#include <vector> 
using namespace std; 

class Node 
{ 
public: 
    Node::Node(char ch) 
    { 
     c = ch; 
     next = NULL; 
    } 
    char c; 
    Node *next; 
}; 

Node* addNode(Node *tail, char ch) 
{ 
    if(tail == NULL) 
     return new Node(ch); 
    else 
    { 
     Node *newN = new Node(ch); 
     tail->next = newN; 
     return newN; 
    } 
} 

void deleteNode(char ch, Node** head, Node**tail) 
{ 
    Node *prev = NULL; 
    Node *cur = *head; 

    while(cur!=NULL) 
    { 
     if(cur->c == ch) 
     { 
      // found cut it 
      if(prev == NULL) 
      { 
       // head cut off 
       if(*tail == *head) 
       { 
        // worst possible, just one element 
        delete *head; 
        *head = NULL; 
        return; 
       } 
       else 
       { 
        // Head cut off but not just first element 
        Node *tmp = *head; 
        *head = (*head)->next; 
        delete tmp; 
        return; 
       } 
      } 
      else 
      { 
       // delete normal node 
       if(*tail == cur) 
       { 
        // delete tail 
        Node *tmp = *tail; 
        *tail = prev; 
        delete tmp; 
        return; 
       } 
       else 
       { 
        // Normal node not tail 
        prev->next = cur->next; 
        delete cur; 
        return; 
       } 
      } 
     } 
     // no match keep searching 
     prev = cur; 
     cur = cur->next; 
    } 
} 

int main() 
{ 
    char str[] = "total"; 
    char htable[26]; 

    memset(htable, 0, sizeof(char)*26); 

    Node *head = NULL; 
    Node *tail = head; 

    for(unsigned int i=0;;i++) 
    { 
     if(str[i] == '\0') 
      break; 

     // check first match 
     char m = htable[str[i]-'a']; 
     switch(m) 
     { 
     case 0: 
      { 
       // first time, add it to linked list 
       htable[str[i]-'a']++; 
       tail = addNode(tail, str[i]); 
       if(head == NULL) 
        head = tail; 
      }break; 
     case 1: 
      { 
       // bam, cut it out 
       htable[str[i]-'a']++; 
       deleteNode(str[i], &head, &tail); 
      }break; 
     } 

    } 

    if(head != NULL) 
     printf("First char without repetition: %c", head->c); 
    else 
     printf("No char matched"); 

    return 0; 
} 

и он работает (хотя я и не освобождает память в конце программы для связанного списка). В основном я сохраняю хэш-таблицу с 0, если символ еще не найден, 1, если он был найден один раз (и добавлен в связанный список в позиции хвоста) и 2, если есть хотя бы два его появления (и должен быть удален связанным списком).

Что такое вычислительная сложность этой программы с обозначением «большой О»?

Поскольку этот алгоритм просто проходит один раз для каждого элемента, я думаю, что это O (n), хотя удаление значений в связанном списке (в худшем случае) потребует дополнительного O (k^2), где k это длина используемого алфавита. Что-то вроде O (n + k^2), это мой выбор, и если строка очень длинная, а алфавит ограничен, алгоритм становится очень эффективным.

Answer 1

Ну, да, на поверхности это выглядит как сложность, но вы ввели нежелательную неэффективность, используя динамическое распределение.

Однако, поскольку вы вызываете deleteNode, и это необходимо для поиска по списку, у вас больше нет сложности O(N).

Подумайте, что произойдет, если у вас есть строка:

abcdefghijklmnopqrstuvwxyzzyxwvutsrqponmlkjihgfedcb 

Это имеет сложность примерно O(N*(N-1)/2), потому что каждый deleteNode вызов должен сканировать до конца оставшегося списка.

Все, что вам действительно нужно сделать, - это сканировать строку один раз и сохранить индекс каждого символа (если он еще не найден), а затем сканировать этот массив для самого низкого индекса. Если вам нравится, вы можете использовать индекс -1, чтобы указать, что символ не был встречен. Это будет сложностью O(2N)

Answer 2

Из описания алгоритма: «Он должен быть как минимум O (n), потому что вы не знаете, будет ли символ повторяться, пока вы не прочтете все символы.», Также см.: Find the first un-repeated character in a string.

В вашем алгоритме я не вижу сложности O (k^2) для удаления элементов из связанного списка. Удаление элемента из связанного списка - это O (n) + O (1) = O (n), где O (n) - поиск, O (1) стирание после того, как вы нашли узел.

Поскольку связанный список может содержать только максимум k элементов, удаление принимает O (k). Так как это внутри петли => O (n * k).

Поскольку k является постоянной => O (n) сложностью - однако, он может реализоваться гораздо проще. Опять же, см. https://stackoverflow.com/a/2285561/592636 (с использованием двух массивов).