Någon som har lust att ta ett praktiskt exempel på hur man räknar ut det??
Jag fattar ju typ vad det ÄR men inte hur man applicerar/räknar ut det.
roofie skrev:Nu vaknade jag ju för typ 10 minuter sedan och kanske säger det här åt helvete.
Men jag tror att jag har förstått Ordo som metoden med vilken man beräknar belastningen en åtgärd gör på tiden eller minnet i datorn. N symboliserar listans längd, och listan är den datamängd som ska behandlas. Därefter skriver man Ordo på olika sätt för att överensstämma med vilka operationer som har utförts och vad som skall mätas.
Refferenser:
http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
http://sv.wikipedia.org/wiki/Komplexitetsteori
http://ilearn.dsv.su.se/mod/resource/view.php?id=1479 nya kursmaterialet för denna vecka
public class Upg1 {
private boolean recursiceIsPalindrome(char[] cs, int left, int right){
if(left >= right)
return true;
else if(cs[left] == ' ')
return recursiceIsPalindrome(cs, ++left, right);
else if(cs[right] == ' ')
return recursiceIsPalindrome(cs, left, ++right);
else if(cs[left] == cs[right])
return recursiceIsPalindrome(cs, ++left, ++right);
return false;
}
private boolean iterativeIsPalindrome(char[] cs){
int right = cs.length-1;
for(int left = 0; left <= right;){
if(cs[left] == ' ')
left++;
else if(cs[right] == ' ')
right++;
else if(cs[left] != cs[right])
return false;
else{
right--; left++;
}
}
return true;
}
}
public class Upg2 {
private static java.util.Random rnd = new java.util.Random();
private static void swap(int[] array, int index1, int index2){
int tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;
}
private static void mix(int[] array){
for( int n=0; n < array.length; ++n){
swap(array, n, rnd.nextInt(array.length));
}
}
private static boolean sorted(int[] array){
for( int n = 1; n < array.length; ++n ){
if(array[n] < array[n - 1])
return false;
}
return true;
}
public static void sort(int[] array){
do{
mix(array);
}while(!sorted(array));
}
}
Metodnamn: | Tidskomplexitet: | Minneskomplexitet: |
isEmpty() | O(N4) | O(0) |
toString() | O(N42) | O(N) |
/**
* LinkedList class implements a doubly-linked list.
*/
public class MyLinkedList<AnyType> implements Iterable<AnyType>
{
/**
* Construct an empty LinkedList.
*/
public MyLinkedList( )
{
clear( );
}
/**
* Change the size of this collection to zero.
*/
public void clear( )
{
beginMarker = new Node<AnyType>( null, null, null );
endMarker = new Node<AnyType>( null, beginMarker, null );
beginMarker.next = endMarker;
theSize = 0;
}
/**
* Returns the number of items in this collection.
* @return the number of items in this collection.
*/
public int size( )
{
return theSize;
}
public boolean isEmpty( )
{
return size( ) == 0;
}
/**
* Adds an item to this collection, at the end.
* @param x any object.
* @return true.
*/
public boolean add( AnyType x )
{
add( size( ), x );
return true;
}
/**
* Adds an item to this collection, at specified position.
* Items at or after that position are slid one position higher.
* @param x any object.
* @param idx position to add at.
* @throws IndexOutOfBoundsException if idx is not between 0 and size(), inclusive.
*/
public void add( int idx, AnyType x )
{
addBefore( getNode( idx, 0, size( ) ), x );
}
/**
* Adds an item to this collection, at specified position p.
* Items at or after that position are slid one position higher.
* @param p Node to add before.
* @param x any object.
* @throws IndexOutOfBoundsException if idx is not between 0 and size(), inclusive.
*/
private void addBefore( Node<AnyType> p, AnyType x )
{
Node<AnyType> newNode = new Node<AnyType>( x, p.prev, p );
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
}
/**
* Returns the item at position idx.
* @param idx the index to search in.
* @throws IndexOutOfBoundsException if index is out of range.
*/
public AnyType get( int idx )
{
return getNode( idx ).data;
}
/**
* Changes the item at position idx.
* @param idx the index to change.
* @param newVal the new value.
* @return the old value.
* @throws IndexOutOfBoundsException if index is out of range.
*/
public AnyType set( int idx, AnyType newVal )
{
Node<AnyType> p = getNode( idx );
AnyType oldVal = p.data;
p.data = newVal;
return oldVal;
}
/**
* Gets the Node at position idx, which must range from 0 to size( ) - 1.
* @param idx index to search at.
* @return internal node corrsponding to idx.
* @throws IndexOutOfBoundsException if idx is not between 0 and size( ) - 1, inclusive.
*/
private Node<AnyType> getNode( int idx )
{
return getNode( idx, 0, size( ) - 1 );
}
/**
* Gets the Node at position idx, which must range from lower to upper.
* @param idx index to search at.
* @param lower lowest valid index.
* @param upper highest valid index.
* @return internal node corrsponding to idx.
* @throws IndexOutOfBoundsException if idx is not between lower and upper, inclusive.
*/
private Node<AnyType> getNode( int idx, int lower, int upper )
{
Node<AnyType> p;
if( idx < lower || idx > upper )
throw new IndexOutOfBoundsException( "getNode index: " + idx + "; size: " + size( ) );
if( idx < size( ) / 2 )
{
p = beginMarker.next;
for( int i = 0; i < idx; i++ )
p = p.next;
}
else
{
p = endMarker;
for( int i = size( ); i > idx; i-- )
p = p.prev;
}
return p;
}
/**
* Removes an item from this collection.
* @param idx the index of the object.
* @return the item was removed from the collection.
*/
public AnyType remove( int idx )
{
return remove( getNode( idx ) );
}
/**
* Removes the object contained in Node p.
* @param p the Node containing the object.
* @return the item was removed from the collection.
*/
private AnyType remove( Node<AnyType> p )
{
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
return p.data;
}
/**
* Returns a String representation of this collection.
*/
public String toString( )
{
StringBuilder sb = new StringBuilder( "[ " );
for( AnyType x : this )
sb.append( x + " " );
sb.append( "]" );
return new String( sb );
}
/**
* Obtains an Iterator object used to traverse the collection.
* @return an iterator positioned prior to the first element.
*/
public java.util.Iterator<AnyType> iterator( )
{
return new LinkedListIterator( );
}
/**
* This is the implementation of the LinkedListIterator.
* It maintains a notion of a current position and of
* course the implicit reference to the MyLinkedList.
*/
private class LinkedListIterator implements java.util.Iterator<AnyType>
{
private Node<AnyType> current = beginMarker.next;
private boolean okToRemove = false;
public boolean hasNext( )
{
return current != endMarker;
}
public AnyType next( )
{
if( !hasNext( ) )
throw new java.util.NoSuchElementException( );
AnyType nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}
public void remove( )
{
if( !okToRemove )
throw new IllegalStateException( );
MyLinkedList.this.remove( current.prev );
okToRemove = false;
}
}
/**
* This is the doubly-linked list node.
*/
private static class Node<AnyType>
{
public Node( AnyType d, Node<AnyType> p, Node<AnyType> n )
{
data = d; prev = p; next = n;
}
public AnyType data;
public Node<AnyType> prev;
public Node<AnyType> next;
}
private int theSize;
private Node<AnyType> beginMarker;
private Node<AnyType> endMarker;
}
class TestLinkedList
{
public static void main( String [ ] args )
{
MyLinkedList<Integer> lst = new MyLinkedList<Integer>( );
for( int i = 0; i < 10; i++ )
lst.add( i );
for( int i = 20; i < 30; i++ )
lst.add( 0, i );
lst.remove( 0 );
lst.remove( lst.size( ) - 1 );
System.out.println( lst );
java.util.Iterator<Integer> itr = lst.iterator( );
while( itr.hasNext( ) )
{
itr.next( );
itr.remove( );
System.out.println( lst );
}
}
}
roofie skrev:Jag må vara lite m4d_n'Crazy.. Men jag avskyr när man lägger upp en bild av Kod.Så jag lägger upp uppgiftens kod i kod.
Tanax skrev:Gick på handledningen idag, fattar allting nu - typ. Rekommenderas till nästa uppgift!
Thx for the help (Y)roofie skrev:Om din bas ligger på att förklara vad "iterativ" och "rekursiv" innebär tror inte jag att en halv dag kommer att vara nog för att både lära sig begreppen och att lösa uppgifterna ens om du jobbar konstant under den tiden.
Sad story is sad.
Jag är själv inte klar med uppgiften, och jag är inte ute efter att skälpa.XistenZ skrev:Thx for the help (Y)roofie skrev:Om din bas ligger på att förklara vad "iterativ" och "rekursiv" innebär tror inte jag att en halv dag kommer att vara nog för att både lära sig begreppen och att lösa uppgifterna ens om du jobbar konstant under den tiden.
Sad story is sad.
roofie skrev:Nu har jag äntligen skickat in, satt flera timmar inatt o nästlade upp de sista beroendena ;p
Sirap skrev:roofie skrev:Nu har jag äntligen skickat in, satt flera timmar inatt o nästlade upp de sista beroendena ;p
Fick du sju O(n) i tid, och en O(n) i minne?
Tanax skrev:Sirap skrev:roofie skrev:Nu har jag äntligen skickat in, satt flera timmar inatt o nästlade upp de sista beroendena ;p
Fick du sju O(n) i tid, och en O(n) i minne?
Jag fick 8 O(n) i tid och 1 O(n) i minne vilka funktioner fick du?
Sirap skrev:Tanax skrev:Sirap skrev:roofie skrev:Nu har jag äntligen skickat in, satt flera timmar inatt o nästlade upp de sista beroendena ;p
Fick du sju O(n) i tid, och en O(n) i minne?
Jag fick 8 O(n) i tid och 1 O(n) i minne vilka funktioner fick du?
Titta närmare på en av add-metoderna ;-) Jag fick också 8 först men upptäckte det efter en stund...
Fast nu ändrade jag toString till typ omega(n) i minne och tid, kändes för slappt att anta att AnyType.toString var konstant, går ju inte riktigt att svara på den känns det som
Tanax skrev:Sirap skrev:Tanax skrev:Sirap skrev:roofie skrev:Nu har jag äntligen skickat in, satt flera timmar inatt o nästlade upp de sista beroendena ;p
Fick du sju O(n) i tid, och en O(n) i minne?
Jag fick 8 O(n) i tid och 1 O(n) i minne vilka funktioner fick du?
Titta närmare på en av add-metoderna ;-) Jag fick också 8 först men upptäckte det efter en stund...
Fast nu ändrade jag toString till typ omega(n) i minne och tid, kändes för slappt att anta att AnyType.toString var konstant, går ju inte riktigt att svara på den känns det som
Huh ? Båda add ska väl vara O(n)? Den första add kallar på den andra add och den andra add kallar på getNode #2 som är O(n) >.<
Angående toString metoden hade jag den som O(n) på både minne och tid från början
Hade du alltså ytterligare 1 O(n) i minne utöver toString?
|
|