Kaip rasti algoritmo laiko sudėtingumą

Klausimas

Kaip rasti algoritmo laiko sudėtingumą?

Ką aš padariau prieš paskelbiant SO klausimą?

Aš tai išlaikiau, tai ir daug kitų nuorodų

Bet ne, kur galėčiau rasti aiškų ir tiesioginį paaiškinimą, kaip apskaičiuoti laiko sudėtingumą.

Ką aš žinau

Pasakykite, kad kodas yra toks paprastas kaip toliau:

 char h = 'y'; // This will be executed 1 time int abc = 0; // This will be executed 1 time 

Pasakykite tokią kilpą kaip:

 for (int i = 0; i < N; i++) { Console.Write('Hello World !'); } 

int i = 0; Tai bus daroma tik vieną kartą . Laikas faktiškai apskaičiuojamas i=0 , o ne deklaracija.

i <n; Tai bus daroma N + 1 kartus.

I ++ Tai bus daroma N kartus.

Taigi, šiuo ciklu reikalingų operacijų skaičius yra

{1+ (N + 1) + N} = 2N + 2

Pastaba Tai gali būti neteisinga, nes aš nesu įsitikinęs, kad suprantu laikinąjį sudėtingumą.

Ką aš noriu žinoti?

Gerai, taigi, šie maži pagrindiniai skaičiavimai, manau, žinau, bet daugeliu atvejų aš pastebėjau laiko sudėtingumą, nes

O (N), O (n2), O (log n), O (n!) .... ir daugelis kitų ,

Ar kas nors gali padėti man suprasti, kaip apskaičiuoti algoritmo laiko sudėtingumą? Esu tikras, kad yra daug naujokų, kaip ir aš noriu žinoti.

724
14 июня '12 в 14:21 2012-06-14 14:21 Yasser yra nustatytas birželio 14 d. 12:21 val. 2012-06-14 14:21
@ 10 atsakymų

Kaip rasti algoritmo laiko sudėtingumą

Pridėsite, kiek mašinų instrukcijų jis atliks priklausomai nuo įvesties dydžio, o tada supaprastins išraišką į didžiausią (kai N yra labai didelis) ir gali apimti bet kokį paprastesnį pastovų faktorių.

Pavyzdžiui, pažiūrėkime, kaip supaprastinti 2N + 2 mašinų instrukcijas, kad ją apibūdintume kaip tik O(N) .

Kodėl mes pašaliname du 2 ?

Esame suinteresuoti algoritmo veikimu, nes N tampa didelis.

Apsvarstykite du narius 2N ir 2.

Kokia yra šių dviejų terminų santykinė įtaka, kai N tampa didelė? Tarkime, N yra milijonas.

Tada pirmasis terminas yra 2 milijonai, o antrasis - tik 2.

Dėl šios priežasties viską išmesti, išskyrus didžiausius narius dideliam N.

Taigi dabar mes nuvažiavome nuo 2N + 2 iki 2N .

Tradiciškai mus domina tik nuolatiniai veiksniai.

Tai reiškia, kad nesirūpiname, jei N yra didelis pastovus veikimo skirtumo daugiklis. Bet kuriuo atveju 2N blokas nėra apibrėžtas pirmiausia. Taigi, mes galime daugintis ar padalyti pastoviu koeficientu, kad pereitume prie paprasčiausios išraiškos.

Taigi 2N tampa tik N

322
14 июня '12 в 14:25 2012-06-14 14:25 atsakymą Andrew Tomazosas pateikė birželio 14 d. 12 d. 2:25 val. 2012-06-14 14:25

Tai puikus straipsnis: http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

Toliau pateiktas atsakymas nukopijuojamas iš viršaus (jei bankrutuoja puikus ryšys)

Dažniausiai metas sudėtingumui apskaičiuoti yra „Big O“ žymėjimas, kuris pašalina visus pastovius veiksnius, todėl darbo laiką galima apskaičiuoti pagal N, kai N artėja prie begalybės. Apskritai tai galite galvoti taip:

 statement; 

Nuolat. Instrukcijos vykdymo laikas nesikeis, palyginti su N.

 for ( i = 0; i < N; i++ ) statement; 

Yra tiesinė. Kontūro veikimo laikas yra tiesiogiai proporcingas N. Kai N yra padvigubintas, taip pat atliekamas veikimo laikas.

 for ( i = 0; i < N; i++ ) { for ( j = 0; j < N; j++ ) statement; } 

Kvadratinė. Dviejų kilpų veikimo laikas yra proporcingas N kvadratui. Kai N yra padvigubintas, važiavimo laikas padidėja N * N.

 while ( low <= high ) { mid = ( low + high ) / 2; if ( target < list[mid] ) high = mid - 1; else if ( target > list[mid] ) low = mid + 1; else break; } 

Logaritminiai. Algoritmo veikimo laikas yra proporcingas kartų skaičiui, kai N gali būti padalintas iš 2. Taip yra dėl to, kad algoritmas padalija darbo erdvę per pusę su kiekvienu iteracija.

 void quicksort ( int list[], int left, int right ) { int pivot = partition ( list, left, right ); quicksort ( list, left, pivot - 1 ); quicksort ( list, pivot + 1, right ); } 

Ar N * log (N). Vykdymo laikas susideda iš N ciklų (iteracinių arba rekursinių), kurie yra logaritminiai, todėl algoritmas yra linijinio ir logaritminio derinys.

Apskritai, kažkas su kiekvienu elementu vienoje dimensijoje yra tiesinė, kažkas su kiekvienu elementu dviem matmenimis yra kvadratinė, o darbo srities padalijimas yra pusiau logaritminis. Yra ir kitų Big O dimensijų, tokių kaip kubinis, eksponentinis ir kvadratinis šaknis, tačiau jie nėra tokie dažni. Pavadinimas „Big O“ apibūdinamas kaip O (), kur yra matas. Greitas rūšiavimo algoritmas bus aprašytas kaip O (N * log (N)).

Atkreipkite dėmesį, kad nė vienoje iš jų neatsižvelgiama į geriausias, vidutines ir blogiausias priemones. Kiekvienas turės savo „Big O“ žymėjimą, taip pat atkreipkite dėmesį, kad tai labai paprastas paaiškinimas. Didžioji O yra labiausiai paplitusi, tačiau ji taip pat yra sudėtingesnė nei aš. Yra ir kitų pavadinimų, pvz., Didelis omega, mažas o ir didelis teta. Tikriausiai joms nepavyks susidurti ne pagal algoritmo analizę.

342
18 янв. atsakymas pateiktas Achow 18 jan. 2013-01-18 13:04 '13, 13:04 2013-01-18 13:04

Iš čia - Įvadas į algoritmo sudėtingumą

1. Įvadas

Kompiuterių moksle algoritmo laiko sudėtingumas kiekybiškai apibrėžia, kiek laiko reikia algoritmui atlikti, kaip įvesties duomenis atitinkančios eilutės ilgio funkcija.

2. Didelis apie įrašą

Algoritmo laiko sudėtingumas paprastai išreiškiamas naudojant didelį O žymėjimą, kuris išskiria mažesnio eilės koeficientus ir terminus. Tokiu būdu išreiškiama, kad laikinasis sudėtingumas yra aprašytas asimptotiniu būdu, t.y. Įvesties signalo dydis yra begalinis.

Pvz., Jei laikas, kurio reikalaujama algoritme visuose n dydžio įvestyse, yra ne daugiau kaip 5n 3 + 3n, asimptotinio laiko sudėtingumas yra O (n 3 ). Daugiau apie tai vėliau.

Kiti pavyzdžiai:

  • 1 = O (n)
  • n = O (n 2 )
  • log (n) = O (n)
  • 2 n + 1 = O (n)

3. O (1) pastovus laikas:

Sakoma, kad algoritmas veikia pastoviu laiku, jei jam reikia tokio pat laiko, nepriklausomai nuo įvesties dydžio.

Pavyzdžiai:

  • masyvas: prieiga prie bet kurio elemento
  • fiksuoto dydžio stack: push ir pop metodai
  • fiksuoto dydžio eilė: Enqueue ir dequeue metodai

4. O (n) linijinis laikas

Sakoma, kad algoritmas veikia linijiniu laiku, jei jo vykdymo laikas yra tiesiogiai proporcingas įvesties dydžiui, ty laikas didėja tiesiškai su didėjančiu įvesties dydžiu.

Apsvarstykite šiuos pavyzdžius: žemiau aš tiesiškai ieško elemento, turinčio laiko kompleksą O (n).

 int find = 66; var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 }; for (int i = 0; i < numbers.Length - 1; i++) { if(find == numbers[i]) { return; } } 

Daugiau pavyzdžių:

  • „Array“: tiesinė paieška, judėjimas, minimali paieška ir kt.
  • „ArrayList“: yra metodas
  • Eilė: yra metodas

5. O (log n) Logaritminis laikas:

Manoma, kad algoritmas veikia logaritminiu laiku, jei jo vykdymo laikas yra proporcingas įvesties dydžio logaritmui.

Pavyzdys: dvejetainė paieška

Prisiminti žaidimą „dvidešimt klausimų“ - užduotis yra atspėti paslėpto skaičiaus reikšmę intervale. Kiekvieną kartą, kai spėliojate, jums sakoma, jei jūsų spėjimas yra per didelis arba per mažas. Dvidešimt klausimų žaidimas apima strategiją, kuri naudoja jūsų spėjimų skaičių perpus pertrauka. Tai yra bendro problemų sprendimo metodo, žinomo kaip dvejetainė paieška, pavyzdys.

6. O (n2) kvadratinis laikas

Manoma, kad algoritmas vykdomas kvadratiniu laiku, jei jo vykdymo laikas yra proporcingas įvesties dydžio kvadratui.

Pavyzdžiai:

7. Kai kurios naudingos nuorodos

121
27 марта '14 в 16:14 2014-03-27 16:14 atsakymą pateikė Yasser, kovo 27 d. 14, 14:14 2014-03-27 16:14

Nors yra atsakymų į šį klausimą. Norėčiau pateikti dar vieną atsakymą su keliais loop pavyzdžiais.

  • O (n) : laiko ciklo sudėtingumas yra traktuojamas kaip O (n), jei ciklo kintamieji padidėja / mažėja pastovia verte. Pavyzdžiui, toliau išvardytos funkcijos turi O (n) laiko sudėtingumą.

     // Here c is a positive integer constant for (int i = 1; i <= n; i += c) { // some O(1) expressions } for (int i = n; i > 0; i -= c) { // some O(1) expressions } 
  • O (n ^ c) : įdėtų kilpų laiko sudėtingumas yra lygus kartų skaičiui, kada yra įvykdytas vidinis pareiškimas. Pvz., Šiose pavyzdžių kontūrose yra laiko sudėtingumas O (n ^ 2)

     for (int i = 1; i <=n; i += c) { for (int j = 1; j <=n; j += c) { // some O(1) expressions } } for (int i = n; i > 0; i += c) { for (int j = i+1; j <=n; j += c) { // some O(1) expressions } 

    Pavyzdžiui, rūšiavimo rūšiavimas ir rūšiavimas turi O laiko sudėtingumą (n ^ 2).

  • O (Logn) laikas Ciklo sudėtingumas laikomas O (Logn), jei ciklo kintamieji yra padalinti / padauginti iš pastovios vertės.

     for (int i = 1; i <=n; i *= c) { // some O(1) expressions } for (int i = n; i > 0; i /= c) { // some O(1) expressions } 

    Pavyzdžiui, dvejetainėje paieškoje yra laiko sudėtingumas O (Logn).

  • O (LogLogn) laikas Ciklo sudėtingumas yra traktuojamas kaip O (LogLogn), jei ciklo kintamieji yra mažinami / didinami eksponentiškai pagal pastovią vertę.

     // Here c is a constant greater than 1 for (int i = 2; i <=n; i = pow(i, c)) { // some O(1) expressions } //Here fun is sqrt or cuberoot or any other constant root for (int i = n; i > 0; i = fun(i)) { // some O(1) expressions } 

Vienas laiko komplekso analizės pavyzdys

 int fun(int n) { for (int i = 1; i <= n; i++) { for (int j = 1; j < n; j += i) { // Some O(1) task } } } 

Analizė :

For i = 1, the inner loop is executed n times. For i = 2, the inner loop is executed approximately n/2 times. For i = 3, the inner loop is executed approximately n/3 times. For i = 4, the inner loop is executed approximately n/4 times. ……………………………………………………. For i = n, the inner loop is executed approximately n/n times.

Taigi algoritmo bendras laiko sudėtingumas yra didesnis (n + n/2 + n/3 + … + n/n) , kuris tampa n * (1/1 + 1/2 + 1/3 + … + 1/n)

Svarbus dalykas serijoje (1/1 + 1/2 + 1/3 + … + 1/n) yra O (Logn). Taigi minėto kodo laiko sudėtingumas yra O (nLogn).


Nuoroda: 1 2 3

81
02 нояб. atsakymas duotas vasario 02 d. 2015-11-02 12:31 '15, 12:31 pm 2015-11-02 12:31

Laiko sudėtingumas su pavyzdžiais

1 - Pagrindinės operacijos (aritmetinis, palyginimas, prieiga prie masyvo elementų, priskyrimas): veikimo laikas visada yra pastovus O (1)

Pavyzdys:

 read(x) // O(1) a = 10; // O(1) a = 1.000.000.000.000.000.000 // O(1) 

2 - Jei tada kitas pareiškimas: atlieka tik maksimalų dviejų ar daugiau galimų pareiškimų veikimo laiką.

Pavyzdys:

 age = read(x) // (1+1) = 2 if age < 17 then begin // 1 status = "Not allowed!"; // 1 end else begin status = "Welcome! Please come in"; // 1 visitors = visitors + 1; // 1+1 = 2 end; 

Taigi, pirmiau minėto pseudokodo T (n) = 2 + 1 + max (1, 1 + 2) = 6. sudėtingumas, taigi, jo didelis oh vis dar išlieka pastovus T (n) = O (1).

3 - Looping (už, o, pakartokite): šio pareiškimo vykdymo laikas yra ciklų skaičius, padaugintas iš operacijų skaičiaus šiame cikle.

Pavyzdys:

 total = 0; // 1 for i = 1 to n do begin // (1+1)*n = 2n total = total + i; // (1+1)*n = 2n end; writeln(total); // 1 

Taigi, jo sudėtingumas yra T (n) = 1 + 4n + 1 = 4n + 2. Taigi, T (n) = O (n).

4 - Nested loop (ciklinė kilpa): kadangi pagrindinėje kilpoje yra bent viena kilpa, šio pareiškimo vykdymo laikas yra O (n ^ 2) arba O (n ^ 3).

Pavyzdys:

 for i = 1 to n do begin // (1+1)*n = 2n for j = 1 to n do begin // (1+1)n*n = 2n^2 x = x + 1; // (1+1)n*n = 2n^2 print(x); // (n*n) = n^2 end; end; 

Bendras vykdymo laikas

Analizuojant algoritmą, yra tam tikras bendras veikimo laikas:

  • O (1) - pastovus laikas Pastovus laikas reiškia, kad važiavimo laikas yra pastovus, jo neturi įtakos įvesties dydis.

  • O (n) - Linijinis laikas Kai algoritmas įveda n įvesties dydį, jis taip pat atlieka n operacijas.

  • O (log n) - logaritminio laiko algoritmas, turintis O (log n) veikimo laiką, yra šiek tiek greičiau nei O (n). Paprastai algoritmas problemą skirsto į tokio paties dydžio poskyrius. Pavyzdys: dvejetainis paieškos algoritmas, dvejetainis konvertavimo algoritmas.

  • O (n log n) - Linijinis laikas Šis laikas dažnai randamas „atskyrimo ir užkariavimo algoritmuose“, kurie rekursiškai skirsto problemą į sub-galias ir tada sujungia juos n kartus. Pavyzdys: sujungimo rūšiavimo algoritmas.

  • O (n 2 ) - kvadratinis laikas Pažvelkite į Bubble rūšiavimo algoritmą!

  • O (n 3 ) - kubinis laikas Jis turi tą patį principą su O (n 2 ).

  • O (2 n ) - eksponentinis laikas Tai labai lėtas, nes įėjimas tampa didesnis, jei n = 1000.000, T (n) yra 21000.000. Brute Force algoritmas turi šį veikimo laiką.

  • O (n!) - Faktinis laikas, LIAUSI !!! Pavyzdys: problema su pardavėju (tsp)

Paimtas iš šio straipsnio . Labai gerai paaiškinta turėtų skaityti.

66
19 апр. Atsakyti Yasser 19 Bal 2014-04-19 12:36 '14 at 12:36 2014-04-19 12:36

Analizuodami kodą, turite jį analizuoti savo ruožtu, skaičiuodami kiekvieną operaciją / atpažįstant laiko sudėtingumą, galiausiai turite apibendrinti, kad gautumėte visą vaizdą.

Pvz., Galite turėti vieną paprastą ciklą, kurio sudėtingumas yra linijinis, bet vėliau toje pačioje programoje gali būti trimis ciklais su kubiniu sudėtingumu, todėl jūsų programa turės kubinį sudėtingumą . Tai yra augimo principas.

Pažiūrėkime, kokios yra algoritmo laiko sudėtingumo galimybės, galite pamatyti augimo tvarką, apie kurią kalbėjau aukščiau:

  • Pastovus laikas yra augimo tvarka 1 , pavyzdžiui: a = b + c .

  • Logaritminis laikas turi LogN augimo LogN , dažniausiai atsitinka, kai kažką padalijate per pusę (dvejetainė paieška, medžiai, net kilpos) arba kažką padauginkite tuo pačiu būdu.

  • Pavyzdžiui, tiesinė , augimo tvarka N

     int p = 0; for (int i = 1; i < N; i++) p = p + 2; 
  • Linijinė , augimo tvarka n*logN , paprastai randama atskyrimo ir užkariavimo algoritmuose.

  • Kubinis , augimo tvarka N^3 , klasikinis pavyzdys yra trigubas kilpas, kuriame jūs tikrinate visus tripletus:

     int x = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) x = x + 2 
  • Eksponentinė augimo tvarka 2^N paprastai atsiranda, kai atliekate išsamią paiešką, pvz., Patikrinkite tam tikro rinkinio pogrupius.

36
05 июня '16 в 12:43 2016-06-05 12:43 atsakymą pateikė Aleksandar Makragić birželio 5 d. 16 d. 12:43 2016-06-05 12:43

Trumpai tariant, laiko sudėtingumas yra būdas apibendrinti, kaip algoritmo operacijų skaičius arba vykdymo laikas didėja, didėjant įvesties dydžiui.

Kaip ir dauguma dalykų, kokteilis gali padėti mums suprasti.

O (n)

Atvykę į vakarėlį, jums reikia susitvarkyti su kiekvienu asmeniu (atlikti operaciją kiekviename elemente). Didėjant N dalyvių skaičiui, laikas, kurį reikia drebėti kiekviena ranka, didėja kaip O(N) .

Kodėl O(N) , o ne cN ?

Yra skirtumas tarp laiko, kiek reikia rankoms su žmonėmis. Jūs galite ją vidutiniškai nustatyti ir fiksuoti c . Tačiau pagrindinė operacija čia - rankų paspaudimas su visais - visada bus proporcinga O(N) , nepriklausomai nuo to, kas c . Kai aptariame, ar reikia eiti į kokteilių vakarėlį, mes dažnai domisi tuo, kad turėsime susitikti su visais, išskyrus mažiausius duomenis apie tai, kaip šie susitikimai atrodo.

O (N ^ 2)

Švino kokteilis nori, kad tu žaidi kvailą žaidimą, kuriame visi sutinka visus. Todėl turite susitikti su kitais žmonėmis ir, nes kitas žmogus jau susitiko su jumis, jie turi atitikti N-2 ir pan. Šios serijos suma yra x^2/2+x/2 . Didėjant dalyvių skaičiui, terminas „ x^2 tampa labai greitas, todėl viskas viskas paliekama.

O (N ^ 3)

Turėtumėte susitikti su visais kitais, o per kiekvieną susitikimą turėtumėte kalbėti apie visus kitus kambarį.

O (1)

Priimančioji nori ką nors paskelbti. Jie mesti stiklą ir garsiai kalba. Visi juos girdi. Pasirodo, kad nesvarbu, kiek lankytojų yra, ši operacija visada užima tiek pat laiko.

O (log N)

Pranešėjas padėjo visiems prie stalo abėcėlės tvarka. Kur yra Danas? Jūs manote, kad jis turėtų būti tarp Adomo ir Mandy (žinoma, ne tarp Mandy ir Zach!). Atsižvelgiant į tai, ar jis yra tarp George ir Mandy? Ne Jis turi būti tarp Adomo ir Fredo, taip pat tarp Cindy ir Fredo. Ir taip toliau ... mes galime veiksmingai rasti Daną, žiūrėdami pusę šio rinkinio ir tada pusę šio rinkinio. Galiausiai mes žiūrime į žmones O (log_2 N) .

O (N log N)

Pirmiau pateiktame algoritme galite rasti, kur sėdėti prie stalo. Jei prie stalo atvyko didelis skaičius žmonių, vienas po kito, ir visi tai padarė, o tai būtų O (N log N) . Atrodo, kad tai laikas, per kurį reikia surūšiuoti bet kokią prekių kolekciją, kai juos reikia palyginti.

Geriausias / blogiausias atvejis

Jūs atėjote į vakarėlį ir turite rasti Inigo - kiek laiko užtruks? Tai priklauso nuo atvykimo. Jei visi mirksės, jūs esate blogiausiu atveju: tai užtruks O(N) . Tačiau, jei visi sėdi prie stalo, tai tik O(log N) . O gal galite naudoti motociklininkų lenktynininkų galią savininkams, o tai tik O(1) .

Darant prielaidą, kad šeimininkas nėra prieinamas, galime pasakyti, kad „Inigo“ paieškos algoritmas turi mažesnę O(log N) ribą ir viršutinę O(N) ribą, priklausomai nuo šalies būklės, kai atvyksite.

Erdvė ir komunikacija

Tos pačios idėjos gali būti taikomos suprasti, kaip algoritmai naudoja erdvę ar ryšį.

Knutas parašė gerą straipsnį apie pirmąjį pavadinimą „Dainų sudėtingumas“.

2 teorija: Yra savavališkai ilgo dainų, kurių sudėtingumas O (1).

Įrodymas: (dėl Casey ir saulės juostos). Apsvarstykite Sk dainas, apibrėžtas (15), bet su

 V_k = 'That the way,' U 'I like it, ' U U = 'uh huh,' 'uh huh' 

visiems k.

29
14 окт. Richardo atsakymas, pateiktas spalio 14 d 2015-10-14 07:12 '15 at 7:12 2015-10-14 07:12

Žinau, kad šis klausimas yra priešingas, ir čia yra puikių atsakymų, bet norėčiau pasidalinti su kitais už matematiškai mąstančius žmones, kurie suklūs į šį postą. Pagrindinė teorema yra dar vienas naudingas dalykas, kurį reikia žinoti studijuojant sudėtingumą. Nematau to paminėti kituose atsakymuose.

3
04 нояб. atsakymas duodamas Gentian Kasa . 2015-11-04 12:20 '15 at 12:20 2015-11-04 12:20

O (n) yra didelė žymė, naudojama įrašyti algoritmo laiko sudėtingumą. Kai algoritme pridedate įvykdymų skaičių, gausite 2N + 2 išraišką, ši išraiška N yra dominuojantis terminas (terminas turi didžiausią įtaką išraiškai, jei jos vertė didėja arba mažėja). Dabar O (N) yra laiko sudėtingumas, o N - dominuojantis terminas. Pavyzdys

 For i= 1 to n; j= 0; while(j<=n); j=j+1; 

čia bendras vidinės kilpos įvykdymų skaičius yra n + 1, o bendras išorinių kilpų vykdymų skaičius yra n (n + 1) / 2, todėl bendras visų algoritmo n + 1 + n (n + 1/2) = ( n ^ 2 + 3n) / 2. čia n ^ 2 yra dominuojantis terminas, todėl šio algoritmo laiko sudėtingumas yra O (n ^ 2)

2
11 марта '13 в 23:18 2013-03-11 23:18 atsakymą pateikė „ ifra khan “ kovo 13 d. 13 val. 23:18 2013-03-11 23:18

Norėdami gauti idėją apie algoritmą, dažnai tai atlieku eksperimentiškai. Tiesiog pakeiskite „N“ įvestį ir patikrinkite, kiek laiko skaičiuojama. Tam reikia šiek tiek minties, nes big-O apibūdina blogiausią algoritmo sudėtingumą, o blogiausio atvejo suradimas gali būti sunkus.