प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

प्रस्तावना

यदि भवान् ज्ञातुम् इच्छति यत् अन्तरिक्ष/समयजटिलता किम् अस्ति तर्हि भवद्भिः ज्ञातव्यं यत् दत्तांशसंरचना किम् अस्ति ।

एतत् द्वयोः स्तरयोः अवगन्तुं शक्यते । अस्माकं जीवने सर्वत्र आँकडा विद्यते, यथा अन्तर्राष्ट्रीयघटना ये Douyin, Yongzheng इत्यस्य कवचनिष्कासनम् इत्यादिषु उष्णविषयाणि सन्ति अस्माकं उपयोक्तारः यत् द्रष्टुं शक्नुवन्ति तत् आँकडा यत् Douyin बैकएण्ड् सर्वरे संगृह्णाति। परन्तु एतेषां सर्वेषां दत्तांशस्य एकं लक्षणं भवति, अर्थात् ते सर्वे Douyin इत्यस्य उष्णसन्धानसूचौ सन्ति, एषा सूची च उपयोक्तृभ्यः ब्राउज् कर्तुं दत्तांशः नियतस्थाने अस्ति इति सुनिश्चित्य संरचिता अस्ति

तदतिरिक्तं दत्तांशसंरचनाभिः सह एल्गोरिदम् अविभाज्यम् अस्ति । खैर, यथा वयं अधुना एव उक्तवन्तः, दत्तांशसंरचना संरचनायां नियमितरूपेण दत्तांशं संगृह्णाति, अतः संरचनातः दत्तांशं कथं कुशलतया प्राप्तुं शक्यते इति एल्गोरिदम् अस्ति ।

कालजटिलता

एल्गोरिदम् इत्यनेन सह समयजटिलता, अन्तरिक्षजटिलता च भवति । यतो हि सङ्गणकानां स्मृतिः बृहत्तरां बृहत्तरं भवति, अतः अन्तरिक्षजटिलतायाः अपेक्षया कालजटिलता अधिका महत्त्वपूर्णा अस्ति ।अतः प्रथमं कालजटिलतां अवगच्छामः

कल्पना

समयजटिलता, महत्त्वपूर्णः शब्दः समयः अस्ति, अत्र समयः तस्य समयं निर्दिशति यदा कश्चन कार्यक्रमः चालितः भवति यदि समयजटिलता न्यूना भवति तर्हि एल्गोरिदम् उत्तमः इति सिद्धः भवति ।कालजटिलतागणना कार्यसूत्रेण T(N) इत्यनेन व्यक्ता भवति ।

अतः वयम् अस्य कार्यक्रमस्य समयजटिलतायाः पूर्वमेव गणनां कृत्वा इष्टतमसमाधानस्य कोडं किमर्थं न लिखामः? अस्मिन् सङ्गणकस्य विषयाः सन्ति ।

1. यतः कार्यक्रमस्य चालनसमयः संकलनवातावरणेन च चालितयन्त्रस्य विन्यासेन च सम्बद्धः भवति, उदाहरणार्थं, एल्गोरिदम् प्रोग्रामः पुरातनं संकलकं उपयुङ्क्ते
   नूतनेन संकलकेन सह संकलनं नूतनेन संकलकेन सह संकलनं च एकस्मिन् यन्त्रे भिन्नाः चालनसमयाः भवन्ति ।
2. एकस्मिन् एव एल्गोरिदम् प्रोग्रामे पुरातनं न्यूनविन्यासयन्त्रं नूतनं उच्चविन्यासयन्त्रं च उपयुज्य भिन्नाः चालनसमयाः सन्ति ।
3. तथा च कार्यक्रमस्य लेखनानन्तरं एव समयस्य परीक्षणं कर्तुं शक्यते, न तु कार्यक्रमस्य लेखनात् पूर्वं सैद्धान्तिकचिन्तनस्य माध्यमेन गणनां मूल्याङ्कनं च कर्तुं शक्यते।

एकं कोडखण्डं पश्यामः : १.

// 请计算⼀下Func1中count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

यदि भवान् गणनायाः निष्पादनसङ्ख्यायाः आधारेण एतत् कोडं पश्यति तर्हि एतत् भवितुमर्हति:
T (N) = N2 + 2 ∗ N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• एन = 1000 टी (एन) = 1002010

अस्मिन् समये कश्चन अवदत्, किं तत् int count=0 न गणयति;

अत्र वयं अस्माकं सङ्गणकस्य अतिशयेन अवमूल्यनं कुर्मः अस्माकं सङ्गणकस्य CPU प्रति सेकण्ड् शतकोटिवारं निष्पादयितुं शक्नोति अवश्यम्, एषः अल्पः समयः उपेक्षितुं शक्यते । अतः अस्माभिः गणिता समयजटिलता समीचीना नास्ति, केवलं रूक्षानुमानम् एव अस्मिन् समये वयं तस्य प्रतिनिधित्वार्थं नूतनं चिह्नं उपयुञ्ज्महे ।

बिग ओ के असममित संकेतन

Big O संकेतनम् : एतत् गणितीयं चिह्नं भवति यस्य उपयोगः कार्यस्य असममितव्यवहारस्य वर्णनार्थं भवति

अतः अत्र T(N) इव अद्यापि गण्यते वा ? अस्मिन् O गणनानियमाः अन्तर्भवन्ति : १.

1. समयजटिलताकार्यसूत्रे T(N) केवलं उच्चतमक्रमपदानि एव धारयन्ति, निम्नक्रमपदानि च निष्कासितानि भवन्ति, यतः यदा N निरन्तरं वर्धते तदा परिणामे निम्नक्रमपदानां प्रभावः लघुतरः भवति यदा N अनन्तः भवति तदा It उपेक्षितुं शक्यते।
2. यदि उच्चतमक्रमपदं विद्यते 1 नास्ति तर्हि अस्य पदस्य नित्यगुणकं निष्कासयन्तु, यतः यथा यथा N वर्धते तथा तथा अस्य गुणांकस्य परिणामे न्यूनाधिकः प्रभावः भविष्यति यदा N अनन्तः भवति तदा तस्य अवहेलना कर्तुं शक्यते
3. यदि T(N) मध्ये N-सम्बद्धाः वस्तूनि नास्ति अपितु केवलं नित्यवस्तूनि सन्ति तर्हि सर्वाणि योजकनित्यं नित्यं 1 इत्यनेन प्रतिस्थापयन्तु ।

ततः उपर्युक्तं पश्यन्तु T(N)=N^ 2 + 2 ∗ N + 10. अत्र उच्चतमः क्रमः N2 अस्ति, अतः अन्येषां निम्नक्रमानाम् अपसारणं कृत्वा जटिलता (ON^2) अस्ति ।

लघु स्केल चॉपर

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++
k)
{
++count;
}
printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

अत्र T(N)=M+N, तर्हि पुनः O(N) गणयामः अत्र M च N च द्वौ अपि समानक्रमौ स्तः, अतः ते प्रथमनियमस्य अनुपालनं न कुर्वन्ति, द्वितीयतृतीयनियमयोः अनुरूपाः न भवन्ति , अतः o(N+M), तदा कश्चन पृष्टवान्, किं यदि N M इत्यस्मात् बृहत्तरः अस्ति तर्हि अत्र प्रश्नः अस्ति यत् N M इत्यस्मात् बृहत्तरः इति कथं ज्ञायते? किं यदि M N इत्यस्मात् बृहत्तरः अस्ति, अतः वयं केवलं सुरक्षितपक्षे भवितुं अत्र तिष्ठामः।

// 计算strchr的时间复杂度？
const char * strchr ( const char
 * str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '0')
return NULL;
p_begin++;
}
return p_begin;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

अत्र वयं str इत्यस्मिन् वर्णस्य स्थानं अन्विष्यामः अत्र अहं ज्ञानबिन्दुं योजयिष्यामि ।

• अस्माकं O गणना सामान्यतया एल्गोरिदमस्य दुष्टतम-जटिलता भवति ।
  अत्र जटिलतायाः त्रयः स्तराः विभक्तुं शक्यन्ते- १.
  1. उत्तमप्रकरणस्य परिदृश्यम्
  तारस्य प्रथमस्थाने वर्णं अन्वेष्टुं ततः :
  F (N) = 1, जटिलता o(1) अस्ति ।

2. औसतस्थितिः : १.
तारस्य मध्ये वर्णं अन्वेष्टुं तर्हि :
च (न) = न/2,ओ(न/2)

3. दुर्भाग्यपूर्णं परिदृश्यम्
तारस्य अन्तिमस्थाने वर्णं अन्वेष्टुं तर्हि :
च (न) = न,ओ(न) .

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

दुर्भाग्यपूर्णे सन्दर्भे यतः उच्चक्रमः अवशिष्टः भवति तथा च n/2 निष्कासितः भवति (प्रथमः द्रव्यः), गुणांकः (द्वितीयः द्रव्यः) च उपेक्षितः भवति, तस्मात् सः ON^2 भवति

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
1
2
3
4
5
6
7
8

यदा n=2 भवति तदा निष्पादनानां संख्या 1 भवति
यदा n=4 भवति तदा निष्पादनानां संख्या 2 भवति
यदा n=16 भवति तदा निष्पादनानां संख्या 4 भवति
निष्पादनसङ्ख्या x इति कल्पयित्वा ततः २
x = न
अतः निष्पादनानां संख्या : x = log n
अतः: func5 इत्यस्य दुष्टतमः समयजटिलता अस्ति:
ओ(लोग्२ ^न) २.

विभिन्नेषु पुस्तकेषु भिन्नाः अभिव्यक्तिविधयः सन्ति

अन्तरिक्षजटिलता

अन्तरिक्षजटिलतायाः विषये किं द्रष्टव्यं यत् तस्य गणनाप्रतिपादनं अपि O इत्यनेन प्रतिनिधित्वं भवति, तस्य नियमाः च कालजटिलतायाः समानानि नियमत्रयं अनुसरन्ति

सूचना

यदा फंक्शन् चालितं भवति तदा आवश्यकं स्टैक् स्पेस (पैरामीटर्स्, स्थानीयचराः, काश्चन रजिस्टर् सूचना इत्यादयः) संकलनस्य समये निर्धारितः अस्ति, अतः स्पेस जटिलता मुख्यतया फंक्शन् चालितस्य समये स्पष्टतया प्रयुक्तेन अतिरिक्तस्थानेन निर्धारिता भवति .

उदाहरणम् १: १.

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

संकलनस्य समये फंक्शन् स्टैक् फ्रेम निर्धारितम् अस्ति ।
भवद्भिः केवलं रनटाइम् इत्यस्य समये फंक्शन् इत्यनेन अनुरोधितं अतिरिक्तं स्थानं प्रति ध्यानं दातव्यम् ।
BubbleSort कृते अतिरिक्तं अनुप्रयोगस्थानं अस्ति
तत्र विनिमय इत्यादीनां स्थानीयचरानाम् सीमितसंख्या अस्ति, यत् अतिरिक्तस्थानस्य नित्यं परिमाणं उपयुज्यते ।
अतः अन्तरिक्षजटिलता O(1) अस्ति ।