Leela Krishna
Leela Krishna

seuraa

huhti 1, 2019 * 4 min Lue

swift – ohjelmointikielellä …

Part -1:

miksi Tietorakenteet?

nykyaikaisissa sovelluksissa suuri osa algoritmeille luontaisesta teoriasta jää usein huomiotta. Ratkaisuja, jotka kuluttavat suhteellisen pieniä määriä tietoa, päätöksiä tiettyjä tekniikoita tai suunnittelumalleja ei välttämättä ole tärkeää vain saada asioita toimimaan. Kuitenkin yleisö kasvaa niin tiedot. Suuri osa siitä, mitä suuret teknologiayritykset menestyvät, on perillinen kyky tulkita valtavia määriä dataa. Järkevän tiedon avulla käyttäjät voivat muodostaa yhteyden, jakaa, suorittaa tapahtumia ja tehdä päätöksiä.

→ Tietorakenteet :

  • Perustietorakenteet

Pino, jono, Lajittelualgoritmit

  • puut

puut & Binääripuut, Binäärihaku, kasa, kasojen Lajittelu, prioriteettijono

  • kaaviot

graphs, adjacency list, Dijkstran algoritmi, Primin algoritmi

→ Big O notaatio :

asymptoottinen analyysi on prosessi, jossa kuvataan algoritmien tehokkuutta, ja se ilmaistaan yleisesti yleisessä muodossa, joka tunnetaan nimellä Big O notaatio.

  • Ajallinen Monimutkaisuus :

algoritmiin(funktioon) kuluvan ajan määrä, kun sen syötekoko(n) kasvaa.

  • avaruuden monimutkaisuus :

muistin (tilan) määrä, joka tarvitaan algoritmin(funktion) suorittamiseen.

nämä molemmat voidaan ilmaista isona O-Notaationa.

  • yleisimmät Aikakompleksit :

→ vakioaika (O(1)) :-

jatkuva aika-algoritmi on, jolla on sama käyntiaika riippumatta sen syötteestä. Iso O-merkintä tälle on O (1).

→ Lineaarinen aika (O (n)) :-

lineaarinen aika-algoritmi on se, jonka nopeus riippuu sen tulokoosta. Toisin sanoen siitä tulee vähemmän tehokas, kun sen syötteen koko(n) kasvaa.

→ Kvadraattinen aika (O (n2)) :-

sillä tarkoitetaan algoritmia, joka vie aikaa verrannollisuuteen tulon koon neliöön. Se karkaa nopeasti käsistä, kun sen syöttömäärä kasvaa.

→ logaritminen aika (O (log n)) :-

yleinen algoritmi, jolla on o(log n) aikakompleksisuus, on Binäärihaku, jonka rekursiivinen relaatio on T(n/2) + O (1) eli jokaisella myöhemmällä puun tasolla jaetaan ongelma puoleen ja tehdään jatkuvaa lisätyötä.

→ Kvasilineaarinen aika (O (n log n)) :-

algoritmin sanotaan kulkevan kvasilineaarisessa ajassa(jota kutsutaan myös log-lineaariseksi ajaksi), jos T(n) = o (n log^k n) jollekin positiiviselle vakiolle k; linearitminen aika on tapaus k = 1.

esimerkki :

tietorakenne on järjestelmällinen tapa järjestää tietoa, jotta sitä voidaan käyttää tehokkaasti. Seuraavat termit ovat tietorakenteen perustermejä.

  • liittymä-jokaisella tietorakenteella on liittymä. Rajapinta edustaa tietorakenteen tukemien toimintojen joukkoa. Käyttöliittymä tarjoaa vain luettelon tuetuista toiminnoista, parametreista, jotka he voivat hyväksyä ja palauttaa näiden toimintojen tyypin.
  • Implementation-Implementation tarjoaa sisäisen kuvan tietorakenteesta. Toteutuksessa määritellään myös tietorakenteen toiminnassa käytettävät algoritmit.

→ tietorakenteen ominaisuudet:

  • virheettömyys-tietorakenteen toteutuksen tulisi toteuttaa rajapintansa oikein.
  • Time Complexity-ajonaikaisen tai tietorakenteen operaatioiden suoritusajan on oltava mahdollisimman pieni.
  • avaruuden monimutkaisuus-Tietorakenneoperaation muistinkäytön tulisi olla mahdollisimman vähäistä.

→ tietorakenteen tarve:

koska Sovellukset muuttuvat monimutkaisiksi ja datarikkaiksi, on kolme yleistä ongelmaa, jotka Sovellukset kohtaavat nyt-päivässä.

  1. Tiedonhaku-tarkastellaan 1 miljoonan(106) myymälän varastoa. Jos sovelluksen on tarkoitus etsiä kohdetta, sen on etsittävä kohde 1 miljoonasta(106) kohteesta joka kerta, kun hakua hidastetaan. Tiedon kasvaessa haku hidastuu.
  2. Prosessorin nopeus-Prosessorin nopeus, vaikka se on hyvin korkea, laskee rajallisesti, jos tieto kasvaa miljardiin ennätykseen.
  3. useita pyyntöjä-koska tuhannet käyttäjät voivat etsiä tietoja samanaikaisesti www-palvelimelta, nopeakin palvelin epäonnistuu tietoja hakiessaan.

edellä mainittujen ongelmien ratkaisemiseksi Tietorakenteet tulevat pelastamaan. Tiedot voidaan järjestää tietorakenteeseen siten, että kaikkia kohteita ei välttämättä tarvitse etsiä, ja tarvittavat tiedot voidaan etsiä lähes välittömästi.

→ Katsotaanpa Swiftissä Pinokäärintä:

luomme kääreen Swiftin array ympärille, jossa käytämme array-käärettä varastorakenteena. Ryhmät antavat jatkuvaa aikaa(O (1)) lisäyksiä ja poistoja, kun ne suoritetaan ryhmän päästä.

se on FIFO → ensimmäinen First Out-tiedoissa.

esimerkkejä iOS: ssä : UINavigation Pino, Kumoa toiminnot jne.

Vastaa

Sähköpostiosoitettasi ei julkaista.