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

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

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

Вот что я сделал:

#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, если есть хотя бы два вхождения (и должен быть удален связанным списком).

Какова вычислительная сложность этой программы с записью big-O?

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

0

Решение

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

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

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

abcdefghijklmnopqrstuvwxyzzyxwvutsrqponmlkjihgfedcb

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

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

1

Другие решения

Из описания алгоритма:
«Это должно быть как минимум O (n), потому что вы не знаете, будет ли повторяться символ, пока не прочитаете все символы.», Также смотрите: Найти первый неповторенный символ в строке.

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

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

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

1

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector