Mπορει καποιος να δωσει ιδεες με ενα θεμα Δομων Δεδομενων?

[Σαϊνόμπι]

Οποια βοηθεια ευπροσδεκτη!

[taazz]

Σειριακή αναζήτηση.

[Σαϊνόμπι]

Σειριακή αναζήτηση.

Aυτο το καναμε αλλα μας βγαινει η πολυπλοκοτητα λαθος...  O(n^2) και οχι Ο(n+m+k)

[nilosgr]

Πως βγήκε το n^2 ;

Καλά λέει ο φίλος, σειριακή αναζήτηση.

 

1. Ψάξε στα πρώτα n στοιχεία της L1, αν το βρεις τερμάτισε
2. Ψάξε στα πρώτα m στοιχεία της L2, αν το βρεις τερμάτισε
3. Ψάξε στα υπόλοιπα k στοιχεία, αν το βρεις τερμάτισε

Το βήμα 1 κάνει έως και n συγκρίσεις, το βήμα 2 κανείς έως m συγκρίσεις και το βήμα 3 μέχρι k συγκρίσεις. Άρα Ο(n+m+k), με χειρότερη περίπτωση να μην υπάρχει το στοιχείο πουθενά

[albNik]

Πως βγήκε το n^2 ;

Καλά λέει ο φίλος, σειριακή αναζήτηση.

 

1. Ψάξε στα πρώτα n στοιχεία της L1, αν το βρεις τερμάτισε
2. Ψάξε στα πρώτα m στοιχεία της L2, αν το βρεις τερμάτισε
3. Ψάξε στα υπόλοιπα k στοιχεία, αν το βρεις τερμάτισε

Το βήμα 1 κάνει έως και n συγκρίσεις, το βήμα 2 κανείς έως m συγκρίσεις και το βήμα 3 μέχρι k συγκρίσεις. Άρα Ο(n+m+k), με χειρότερη περίπτωση να μην υπάρχει το στοιχείο πουθενά

 

 

Αν συγκρινεις το καθενα της L1 με όλα της L2 βγαινεi Ο(n*m)

 

Edit

Αφου ξερουμε που ειναι ο πρώτος κοινος κομβος n βηματα απο την L1 ή m από την L2.

Σε O(min(n,m)) βηματα χωρις συγκρισεις.

 

Μήπως ηθελε να πει τον τελευταίο κοινο κομβο??

[bnvdarklord]

Μήπως ηθελε να πει τον τελευταίο κοινο κομβο??

 

Αφου ξερουμε οτι εχει μηκος k.

[albNik]

Εχω την εντύπωση m, n, k ειναι τάξη μεγεθους, δεν ειναι γνωστα ακριβώς.

[nilosgr]

Αααα σορι, εγω νομιζα κανει αναζητηση ενος στοιχειου μεσα στις λιστες. πχ βρες την πρωτη εμφανιση του Χ κομβου στην L1 ή την L2.

 

Λοιπον, με καθε επιφυλαξη

ΕΙΣΟΔΟΣ: 
    λιστα L1
    λιστα L2

EΞΟΔΟΣ:  το k

ΑΛΓΟΡΙΘΜΟΣ: find_k
    int k = 0

    if L1.next != NULL
        k = find_k(L1.next, L2)
    else if L2.next != NULL
        k = find_k(L1,L2.next)
    
    if L1.root == L2.root
        k = k + 1

    return k