Ի՞նչ է չափում Big O- ն:

2024 Հեղինակ: Taylor Roberts | [email protected]. Վերջին փոփոխված: 2023-12-16 00:29

մեծ - Օ նշում. (սահմանում) Սահմանում. Տեսական չափել ալգորիթմի կատարման համար, սովորաբար անհրաժեշտ ժամանակը կամ հիշողությունը, հաշվի առնելով խնդրի չափը n, որը է սովորաբար իրերի քանակը: Ոչ ֆորմալ, ասելով f(n) = որոշ հավասարում Օ (g(n)) նշանակում է է g- ի (n) որոշ հաստատուն բազմապատիկից պակաս:

Բացի այդ, ինչ է նշանակում Big O- ն:

Մեծ Օ նշումը օգտագործվում է համակարգչային գիտության մեջ `նկարագրելու ալգորիթմի կատարումը կամ բարդությունը: Մեծ Օ հատուկ նկարագրում է ամենավատ սցենարը և կարող է օգտագործվել նկարագրելու համար պահանջվող կատարման ժամանակը կամ ալգորիթմի կողմից օգտագործվող տարածքը (օրինակ ՝ հիշողության մեջ կամ սկավառակի վրա):

Երկրորդ ՝ Big O- ն ամենավատ դեպքն է: Այսպիսով, երկուական որոնման մեջ լավագույնը գործ է Օ (1), միջին և վատագույն դեպքում է Օ (լոգոն): Մի խոսքով, տիպի որևէ փոխհարաբերություն չկա » մեծ Օ օգտագործվում է վատագույն դեպքում , Theta միջին գործ »: Բոլոր տեսակի նշումները կարող են (և երբեմն օգտագործվում են) լավագույն, միջին կամ վատագույն դեպքում ալգորիթմի.

Բացի վերևից, ո՞րն է Big O գործառույթը:

Մեծ Օ նշումը մաթեմատիկական նշում է, որը նկարագրում է a- ի սահմանափակող վարքը գործառույթը երբ փաստարկը ձգտում է դեպի որոշակի արժեք կամ անսահմանություն: Նկարագրություն ա գործառույթը առումով մեծ Օ նշումը սովորաբար ապահովում է միայն աճի տեմպի վերին սահմանը գործառույթը.

Ինչպե՞ս եք բացատրում Big O նշումը:

The Մեծ O նշում սահմանում է ալգորիթմի վերին սահմանը, այն սահմանափակում է ֆունկցիան միայն վերևից: Օրինակ, հաշվի առեք Insertion Sort- ի դեպքը: Լավագույն դեպքում դա տևում է գծային ժամանակ, իսկ վատագույն դեպքում `քառակուսի ժամանակ: Կարող ենք ապահով ասել, որ Տեղադրման տեսակավորման ժամանակային բարդությունը հետևյալն է Օ (n^2):