5
Ich habe ein Problem in sortierten verknüpften Liste. Ich kann ein Element nicht in konstanter Zeit einfügen. Wenn es möglich ist, wie kann ich es lösen?Wie fügt man ein Objekt in eine sortierte verkettete Liste innerhalb konstanter Zeitkomplexität ein?
Und diese Funktion Zeitkomplexität ist Big-O (N)
template <class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
NodeType<ItemType>* newNode;
NodeType<ItemType>* predLoc;
NodeType<ItemType>* location;
bool moreToSearch;
location = listData;
predLoc = NULL;
moreToSearch = (location != NULL);
while (moreToSearch)
{
if (location->info < item)
{
predLoc = location;
location = location->next;
moreToSearch = (location != NULL);
}
else moreToSearch = false;
}
newNode = new NodeType<ItemType>;
newNode->info = item;
if (predLoc == NULL)
{
newNode->next = listData;
listData = newNode;
}
else
{
newNode->next = location;
predLoc->next = newNode;
}
length++;
}
Sie können nicht wissen. Wenn Sie das tun könnten, hätten Sie die Sortierung revolutioniert. Sie könnten mit einer leeren verketteten Liste beginnen, die per Definition sortiert wäre, das erste noch sortierte Element hinzufügen und dann weitermachen, was bedeuten würde, dass die Sortierelemente O (n), das ist unmöglich. –