Komplexität des ALgorithmus ?

WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

MrEpsilon

Forum-Newbie


	Beiträge: 8

	Anmeldedatum: 18.04.15

	Wohnort: ---

	Version: ---

Verfasst am: 20.04.2015, 22:20 Titel: Komplexität des ALgorithmus ?

Hi,

Hab folgenden Algorithmus implementiert, der Intervalle färben soll. Als Eingabe erhält der Algorithmus die vektoren "anfang" und "ende" mit start-bzw. endpunkten der Intervalle. Ich bin mir nun etwas unsicher bei der Bestimmung der Komplexität:

Code:

.......

%Intervalle nach Startpunkt sortieren:
A=[anfang' ende'];
[~,s_idx]=sort(A(:,1));
A=A(s_idx,:);

%Farben-Pool definieren
%Und Spalte für verwendete Farben deklarieren

Farben=[1:n];
A=[A zeros(n,1)];

%untere Schranke für (rechte) Intervallgrenzen
u=-inf;

for j=1:n

%Test ob Farben wieder frei geworden sind:
R=A(A(1:j,2)<A(j,1),:);
R=R(R(:,2)>=u,:);
% hinzufügen der freigewordenen Farben zum Farben-pool
Farben=union(R(:,3),Farben);

%Färben des aktuellen Intervalls mit der kleinstmöglichen Farbe
A(j,3)=min(Farben);
%diese Farbe aus dem Farben-pool entfernen
Farben=setdiff(Farben,min(Farben));

%neue Schranke für (rechte) Intervallgrenzen
u=A(j,1);

end %for

.......

Funktion ohne Link?

Durch das sortieren habe ich mindestens die Komplexität O(n*log(n)). Habe aber nun meine zweifel ob der Teil:

Code:

%Test ob Farben wieder frei geworden sind:
R=A(A(1:j,2)<A(j,1),:);
R=R(R(:,2)>=u,:);

Funktion ohne Link?

meine Komplexität nicht nach oben schraubt und zu O(n^2) werden lässt ....
Kann mir da wer weiterhelfen?

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 21.04.2015, 08:56 Titel: Re: Komplexität des ALgorithmus ?

Hallo MrEpsilon,

Möchtest Du das effizient programmieren? Dann könnte sinnvoller sein die "Farben" als [1 x n] Logical Vektor zu definieren, und nicht als numerischen Vektor 1:n.

Code:

% A(j,3)=min(Farben);
% Farben=setdiff(Farben,min(Farben));

% einfacher:
[A(j,3), index] = min(Farben);
Farben(index) = [];

Funktion ohne Link?

Oder geht es nur um die Bestimmung der Komplexität?

Gruß, Jan


Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:	Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen

Impressum | Nutzungsbedingungen | Datenschutz | FAQ |

RSS

Hosted by:

Copyright © 2007 - 2025 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.