Suchalgorithmus der Klasse Vector

[Basti4231]

Hey Leute,

ich müsste wissen wie die Komplexität bei der Suche in Vector ausschaut.
Welcher Algorithmus steckt hinter der Suche? Ist es etwa eine lineare Suche?
Habe den ganzen Tag schon gesucht, bin aber nicht wirklich fündig geworden...

lg basti

 

[XHelp]

Schau doch in den Quelltext

 

[Michael...]

von welcher Suche sprichts Du? contains(...)?
Zu den JDK Klassen gibt es auch den Quellcode. Hier findet man z.B:

...
    public boolean contains(Object elem) {
	return indexOf(elem, 0) >= 0;
    }
...
    public synchronized int indexOf(Object elem, int index) {
	if (elem == null) {
	    for (int i = index ; i < elementCount ; i++)
		if (elementData[i]==null)
		    return i;
	} else {
	    for (int i = index ; i < elementCount ; i++)
		if (elem.equals(elementData[i]))
		    return i;
	}
	return -1;
    }...

 

[SlaterB]

welche Suche überhaupt? indexOf scheint nicht sehr intelligent zu sein,
ohne angenommene Sortierung mehr aber auch kaum möglich

    /**
     * Searches for the first occurence of the given argument, beginning 
     * the search at <code>index</code>, and testing for equality using 
     * the <code>equals</code> method. 
     *
     * @param   elem    an object.
     * @param   index   the non-negative index to start searching from.
     * @return  the index of the first occurrence of the object argument in
     *          this vector at position <code>index</code> or later in the
     *          vector, that is, the smallest value <tt>k</tt> such that 
     *          <tt>elem.equals(elementData[k]) && (k &gt;= index)</tt> is 
     *          <tt>true</tt>; returns <code>-1</code> if the object is not 
     *          found. (Returns <code>-1</code> if <tt>index</tt> &gt;= the
     *          current size of this <tt>Vector</tt>.)
     * @exception  IndexOutOfBoundsException  if <tt>index</tt> is negative.
     * @see     Object#equals(Object)
     */
    public synchronized int indexOf(Object elem, int index) {
	if (elem == null) {
	    for (int i = index ; i < elementCount ; i++)
		if (elementData[i]==null)
		    return i;
	} else {
	    for (int i = index ; i < elementCount ; i++)
		if (elem.equals(elementData[i]))
		    return i;
	}
	return -1;
    }

 

[Dit_]

Hey Leute,

ich müsste wissen wie die Komplexität bei der Suche in Vector ausschaut.
Welcher Algorithmus steckt hinter der Suche? Ist es etwa eine lineare Suche?

Ja, O(n)

 

[Basti4231]

merci, das wollte ich wissen

EDIT: Das wäre dann im Average Case O(n/2) und Worst Case O(n) thanks