ঠিক আছে, তাই, গণনীয় জটিলতা. একটি সতর্কতা শুধুমাত্র একটি বিট আমরাও far-- ঝাঁপিয়ে আগে সম্ভবত এই মধ্যে হবেন সবচেয়ে গণিত-ভারী জিনিষ আমরা CS50 মধ্যে সম্পর্কে কথা বলতে. আশা রাখি, এটা খুব অপ্রতিরোধ্য হবে না এবং আমরা চেষ্টা এবং আপনি গাইড করব প্রক্রিয়ার মাধ্যমে, কিন্তু ন্যায্য সতর্কবাণী শুধুমাত্র একটি বিট. একটি সামান্য বিট আছে গণিত এখানে জড়িত. ঠিক আছে, যাতে তাই করতে আমাদের গণনামূলক ব্যবহার বাস্তব world-- তা সত্যিই আলগোরিদিম বুঝতে গুরুত্বপূর্ণ এবং কিভাবে তারা তথ্য প্রক্রিয়া. যদি আমরা সত্যিই একটি দক্ষ আলগোরিদিম, আমরা সম্পদের পরিমাণ হ্রাস করা যাবে আমরা তা মোকাবেলা করার জন্য উপলব্ধ আছে. আমরা একটি অ্যালগরিদম আছে যে কাজ অনেক নিতে যাচ্ছে সত্যিই একটি প্রক্রিয়া তথ্য বৃহৎ সেট, এটা আরো প্রয়োজন যাচ্ছে আরো সম্পদ, এবং যা স্টাফ টাকা, র্যাম, যে সব ধরনের হয়. 

সুতরাং, সক্ষম হচ্ছে একটি বিশ্লেষণ করতে অ্যালগরিদম, এই টুল সেট ব্যবহার মূলত, question-- জিজ্ঞেস এই অ্যালগরিদম স্কেল আছে কিভাবে আমরা এটা আরো এবং আরো তথ্য নিক্ষেপ হিসাবে? CS50, আমরা যে পরিমাণ ডেটা আছেন সাথে কাজ করা হয় খুবই ছোট. সাধারণত, আমাদের প্রোগ্রাম যাচ্ছি একটি দ্বিতীয় বা less-- চালানোর সম্ভবত অনেক কম বিশেষ প্রথম দিকে. 

কিন্তু যে পুলিশ একটি কোম্পানী সম্পর্কে চিন্তা গ্রাহকদের লক্ষ লক্ষ শত শত সঙ্গে. তাঁরা প্রক্রিয়া প্রয়োজন যে গ্রাহকের তথ্য. গ্রাহকদের সংখ্যা হিসাবে তারা আছে, বড় এবং বড় এটা প্রয়োজন যাচ্ছে আরো এবং আরো সম্পদ. কিভাবে আরো অনেক সম্পদ? ওয়েল, যে কিভাবে উপর নির্ভর করে আমরা আলগোরিদিম বিশ্লেষণ, এই টুলবক্স সরঞ্জাম ব্যবহার. আমরা জটিলতা সম্পর্কে কথা বলতে হলে একটি এলগরিদম যা কখনও কখনও আপনি পাবেন এটা সময় হিসাবে উল্লেখ শুনতে জটিলতা বা স্থান জটিলতা কিন্তু আমরা শুধু চলুন complexity-- কল আমরা সাধারণত যে বিষয়ে কথা বলছি খারাপ কেস দৃশ্যকল্প. চরম খারাপ গাদা দেওয়া আমরা এটা নিক্ষেপ করা যেতে পারে যে তথ্য, কিভাবে এই অ্যালগরিদম যাচ্ছে প্রক্রিয়া বা যে তথ্য মোকাবেলা? আমরা সাধারণত খারাপ-ক্ষেত্রে কল একটি অ্যালগরিদম বড়-হে রানটাইম. সুতরাং একটি অ্যালগরিদম বলেন, হতে পারে ছক n বা n হে হে চালানো. আমার এবং আরো কি যারা একটি দ্বিতীয় মধ্যে মানে. 

কিন্তু, মাঝে মাঝে আমরা যত্ন না সর্বোত্তম ক্ষেত্রে দৃশ্যকল্প সম্পর্কে. তথ্য সবকিছু হয় তাহলে কি আমরা চেয়েছিলাম এটা হতে এবং এটা একেবারে নিখুঁত ছিল এবং আমরা এই নিখুঁত পাঠানো হয়েছে আমাদের এলগরিদম মাধ্যমে তথ্য সেট. কিভাবে এটা যে পরিস্থিতি হ্যান্ডেল করবে? আমরা মাঝে মাঝে যে পড়ুন বড়-ওমেগা, বড়-হে বিপরীতে তাই, আমরা বড়-ওমেগা আছে. সর্বোত্তম ক্ষেত্রে দৃশ্যকল্প বিগ-ওমেগা. খারাপ কেস দৃশ্যকল্প জন্য বিগ-হে. সাধারণত, আমরা যে বিষয়ে যখন কথা একটি অ্যালগরিদম জটিলতা, আমরা যে বিষয়ে কথা বলছি খারাপ কেস দৃশ্যকল্প. সুতরাং, এটা মনে রেখো. 

আর এই ক্লাসে, আমরা সাধারণত যাচ্ছেন সরাইয়া কঠোর বিশ্লেষণের ছেড়ে চলে যেতে. বিজ্ঞান এবং ক্ষেত্র আছে উপাদান এই ধরনের অনুগত. আমরা যুক্তি সম্পর্কে কথা বলতে হলে আলগোরিদিম মাধ্যমে, আমরা অনেক জন্য টুকরা বাই টুকরা করব যা আলগোরিদিম আমরা ক্লাসে সম্পর্কে কথা বলতে. আমরা সত্যিই ঠিক যে বিষয়ে কথা বলছি সাধারণ জ্ঞানে এটা মাধ্যমে যুক্তি, না সূত্রে, বা নিদর্শনাবলী নিয়ে, বা যে মত কিছু. তাই চিন্তা করবেন না, আমরা হতে হবে না একটি বড় গণিত বর্গ মধ্যে বাঁক. 

তাই আমি মনে করি আমরা জটিলতা যত্নশীল বলেন এটা প্রশ্ন, কিভাবে জিজ্ঞেস কারণ আমাদের আলগোরিদিম বৃহত্তর হ্যান্ডেল করবেন এবং বৃহত্তর ডেটা সেট তাদের নিক্ষিপ্ত হচ্ছে. ওয়েল, একটি তথ্য সংকলন কি? আমি তখন অনেক বেশি কী বুঝিয়েছিলেন? এটা বেশীর ভাগ যাই হোক না কেন মানে প্রেক্ষাপটে তা, সৎ হতে. আমরা একটি অ্যালগরিদম, থাকে প্রসেস Strings-- আমরা সম্ভবত আছেন স্ট্রিং মাপ বিষয়ে কথা. যে তথ্য আছে set-- আকার, সংখ্যা স্ট্রিং আপ যে অক্ষর. আমরা একটি বিষয়ে কথা বলছি তাহলে ফাইল প্রসেস যে অ্যালগরিদম, আমরা সে বিষয়ে কথা বলা যেতে পারে অনেক কিলোবাইট যে ফাইল গঠিত. এবং যে তথ্য সংকলন. আমরা একটি অ্যালগরিদম যে বিষয়ে কথা বলছি তাহলে যে, আরো সাধারণভাবে অ্যারে হ্যান্ডলগুলি যেমন বাছাই আলগোরিদিম হিসাবে অথবা আলগোরিদিম অনুসন্ধানের জন্য, আমরা সম্ভবত সংখ্যা যে বিষয়ে কথা বলছি একটি অ্যারের গঠিত যে উপাদানের. 

এখন, আমরা একটি পরিমাপ করতে পারেন এলগরিদম বিশেষ করে, যখন আমি বলতে আমরা যা করতে পারেন আমি একটি অ্যালগরিদম পরিমাপ আমরা কিভাবে পরিমাপ করতে পারেন মানে অনেক সম্পদ এটা পর্যন্ত সময় লাগে. যারা সম্পদ আছে কিনা, কতগুলি উপস্থিত RAM- র বাইট অথবা RAM মেগাবাইটে এটি ব্যবহার করে. বা কত সময় এটি চালানোর জন্য লাগে. আর আমরা এই কল করতে পারেন এন এফ, ইচ্ছামত, পরিমাপ. যেখানে n সংখ্যা তথ্য সেটে উপাদানের. আর এন এর F কতগুলি কিছুটা হয়. কত সম্পদের ইউনিট আছে এটা যে তথ্য প্রক্রিয়া করতে প্রয়োজন. 

এখন, আমরা আসলে না যত্ন ঠিক এন এফ কি সম্পর্কে. আসলে, আমরা খুব কমই ইচ্ছার অবশ্যই মৃত্যু কামনা করবে না এই বর্গ আমি কোনো সত্যিই গভীর জলে ডুব চ এন কি বিশ্লেষণ. আমরা শুধু কি F সম্পর্কে কথা বলতে যাচ্ছেন এন আনুমানিক বা কি তা থাকে হয়. একটি আলগোরিদিম প্রবণতা তার সর্বোচ্চ শব্দটি দ্বারা dictated. আর আমরা তা দেখতে পারেন আমি গ্রহণ করে যে অর্থ একটি আরো একটি কংক্রিট উদাহরণ তাকান. 

সুতরাং আসুন আমরা আছে বলা যাক তিনটি ভিন্ন আলগোরিদিম. যা প্রথম এন লাগে সম্পদের ঘনাংকিত, কিছু ইউনিট আকার n একটি তথ্য সংকলন প্রক্রিয়া. আমরা যে সময় লাগে একটি দ্বিতীয় আলগোরিদিম আছে ঘনাংকিত প্লাস n ছক সম্পদ এন আকার n একটি তথ্য সংকলন প্রক্রিয়া. এবং আমরা একটি তৃতীয় আছে যে in-- সঞ্চালিত হয় যে অ্যালগরিদম আপ লাগে ঘনাংকিত n বিয়োগ 8n ছক সম্পদ প্লাস 20 এন ইউনিট একটি অ্যালগরিদম প্রক্রিয়া আকার n সেট তথ্য দিয়ে. 

এখন আবার আমরা সত্যিই যাচ্ছে না বিস্তারিত এই মাত্রা ঢোকা. আমি শুধু এই পর্যন্ত আছে সত্যিই আছি এখানে একটি বিন্দু একটি নিদর্শন হিসাবে আমি হতে যাচ্ছি যে , একটি দ্বিতীয় মধ্যে উপার্জন যা আমরা শুধুমাত্র সত্যিই গুরুত্বপূর্ণ যে হয় কিছু প্রবণতা সম্পর্কে ডেটা সেট বড় পেতে হিসাবে. তথ্য সংকলন ছোট হয়, তাহলে তাই, আছে আসলে একটি চমত্কার বড় পার্থক্য এই আলগোরিদিম মধ্যে. সেখানে তৃতীয় অ্যালগরিদম 13 বার আর লাগে সম্পদের 13 বার পরিমাণ প্রথম এক আত্মীয়ের চালানোর. 

আমাদের তথ্য সংকলন মাপ 10, হয় তাহলে যা বড়, কিন্তু অগত্যা বিশাল নয় আমরা সেখানে দেখতে পারেন আসলে একটি পার্থক্য একটি বিট. তৃতীয় অ্যালগরিদম আরো দক্ষ হয়ে ওঠে. এটা আসলে 40% সম্পর্কে - বা 60% বেশি দক্ষ. এটা 40% সময় পরিমাণ সময় লাগে. এটা নিতে পারবেন run-- পারেন সম্পদের 400 ইউনিট আকার 10 একটি তথ্য সংকলন প্রক্রিয়া. প্রথম যেহেতু অ্যালগরিদম, বিপরীতভাবে, সম্পদের 1,000 ইউনিট লাগে আকার 10 একটি তথ্য সংকলন প্রক্রিয়া. কিন্তু হিসাবে কি চেহারা আমাদের সংখ্যা এমনকি বড় পেতে. 

এখন, পার্থক্য এই আলগোরিদিম মধ্যে একটু কম আপাত পরিণত শুরু. আছে এবং সত্য লোয়ার অর্ডারে terms-- অথবা বরং, কম exponents-- সঙ্গে শর্তাবলী অপ্রাসঙ্গিক হয়ে শুরু. একটি তথ্য সংকলন আকারের হয় তাহলে 1,000 এবং প্রথম অ্যালগরিদম একটি বিলিয়ন পদক্ষেপে চালায়. এবং দ্বিতীয় আলগোরিদিম রান একটি বিলিয়ন এবং একটি মিলিয়ন পদক্ষেপ. আর তৃতীয় অ্যালগরিদম রান একটি বিলিয়ন পদক্ষেপ শুধু লাজুক মধ্যে. এটা অনেক সুন্দর একটি বিলিয়ন পদক্ষেপ. যারা লোয়ার অর্ডারে শর্তাবলী শুরু সত্যিই অপ্রাসঙ্গিক হয়ে. আর শুধু সত্যিই হোম হাতুড়ি point-- ডাটা ইনপুট আকার একটি হল যদি million-- এই সব তিনটি প্রায় কাছাকাছি এক quintillion-- যদি নেওয়া আমার গণিত correct-- পদক্ষেপ একটি ডাটা ইনপুট প্রক্রিয়া আকার একটি মিলিয়ন. একটি পদক্ষেপ যে অনেক. এবং যে তাদের কেউ জানতেও একটি দম্পতি 100,000, বা কয়েক সেকেন্ড সময় লাগতে 100 মিলিয়ন এমনকি কম হলে আমরা একটি সংখ্যা যে বিষয়ে কথা বলছি যে এটা কোন ধরনের অপ্রাসঙ্গিক big--. তারা সব সময় নিতে ঝোঁক প্রায় ঘনাংকিত n, এবং তাই আমরা আসলে পড়ুন হবে এই আলগোরিদিম সমস্ত যাও এন অনুক্রম হচ্ছে ঘনাংকিত বা n ঘনাংকিত বড়-হে. 

এখানে আরো কিছু একটা তালিকা সাধারণ গণনীয় জটিলতা ক্লাস আমরা সম্মুখীন হবেন যে আলগোরিদিম, সাধারণত. এবং এছাড়াও বিশেষভাবে CS50 মধ্যে. এই থেকে আদেশ হয় সাধারণত উপরের দ্রুততম, নীচে সাধারণত ধীরতম করতে. সুতরাং ধ্রুবক সময় আলগোরিদিম ঝোঁক নির্বিশেষে, দ্রুততম হতে আকার ডাটা ইনপুট আপনি পাস. তারা সবসময় একটি অপারেশন করা বা মোকাবেলা করতে সম্পদের এক ইউনিট. এটি 2 হতে পারে, এটা হতে পারে 3 হতে, এটা 4 হতে পারে. কিন্তু এটা একটি ধ্রুব সংখ্যা. এটা পরিবর্তিত হয় না. 

লগারিদমিক সময় আলগোরিদিম সামান্য ভাল হয়. আর একটি সত্যিই ভাল উদাহরণ একটি লগারিদমিক সময় এলগরিদম আপনি নিশ্চয় এখন দ্বারা দেখা করেছি ফোনবুকের পৃথক্ বিচ্ছিন্নকরণ ফোনবুকে মাইক স্মিথ এটি. আমরা অর্ধেক সমস্যা কাটা. আর এন বৃহত্তর পায় তাই হিসাবে এবং বড় এবং larger-- আসলে, প্রত্যেক সময় আপনি দ্বিগুণ এন, এটি শুধুমাত্র একটি পদক্ষেপ নেয়. যে অনেক ভাল তাই বেশী, বলে, রৈখিক সময়. আপনি এন দ্বিগুণ হলে যা তা, হয় ধাপ সংখ্যা দ্বিগুণ লাগে. আপনি এন ট্রিপল তাহলে, এটা লাগে ধাপের সংখ্যা ট্রিপল. ইউনিট প্রতি এক ধাপ. 

তারপর জিনিষ একটু more-- পেতে একটু কম দুর্দান্ত সেখান থেকে. আপনি কখনও কখনও, রৈখিক নাচুনে সময় আছে পাসওয়ার্ড ভুলে গেছেন? রৈখিক সময় বলা অথবা এন এন লগ ইন করুন. এবং আমরা একটি উদাহরণ হবে একটি অ্যালগরিদম যে এখনও ভালো, যা n log n, রান তুলনায় দ্বিঘাত সময়ের মধ্যে ছক. অথবা বহুপদী সময়, এন দুই দুটি তার চেয়ে অনেক বেশী কোন সংখ্যা. অথবা সূচকীয় সময়, যা এমনকি worse-- সি এন হয়. তাই কিছু ধ্রুব সংখ্যা উত্থাপিত ইনপুট মাপ শক্তি. সুতরাং যদি 1,000-- আছে যদি ডাটা ইনপুট, আকার 1,000 হয় এটা 1000 তম ক্ষমতায় সি নিতে হবে. এটা বহুপদী সময় চেয়ে অনেক খারাপ. 

গুণিতক সময় এমনকি খারাপ হয়. এবং বাস্তবিকই, সত্যিই আছে কি অসীম সময় আলগোরিদিম অস্তিত্ব, যার যেমন তথাকথিত, হিসাবে মূঢ় sort-- পেশা এলোমেলোভাবে একটি অ্যারের পরিহার হয় এবং তারপর দেখতে পরীক্ষা কিনা তা সাজানো. এবং এটি এলোমেলোভাবে, না হলে আবার অ্যারের পরিহার এবং এটি সাজানো কিনা তা দেখার জন্য পরীক্ষা. এবং হিসাবে আপনি সম্ভবত imagine-- পারেন আপনি একটি অবস্থা কল্পনা করতে পারেন যেখানে খারাপ-ক্ষেত্রে, যে ইচ্ছা আসলে অ্যারে দিয়ে শুরু না. যে অ্যালগরিদম সব সময় চালানো হবে. তাই এমন একটি হবে অসীম সময় এলগরিদম. আশা রাখি, আপনার লেখা হবে না কোনো গৌণিক বা অসীম সময় CS50 মধ্যে আলগোরিদিম. 

সুতরাং, আসুন নিতে দিন একটু বেশি কিছু সহজ যেন কংক্রিটের বর্ণন গণনীয় জটিলতা শ্রেণীর. সুতরাং আমরা একটি example-- আছে বা দুটি উদাহরণ এখানে ধ্রুব সময় আলগোরিদিম, যা সবসময় নেওয়া খারাপ-ক্ষেত্রে একটি অপারেশন. প্রথম example-- তাই আমরা একটি ফাংশন আছে আপনার জন্য 4 বলা যা আকার 1,000 একটি অ্যারের লাগে. কিন্তু তারপর দৃশ্যত আসলে চেহারা না এটিকে সত্যিই কি গ্রাহ্য না করে এ , এটি ভেতরে যে অ্যারের. সর্বদা মাত্র চার ফেরৎ. সুতরাং, যে অ্যালগরিদম, এটা সত্ত্বেও 1,000 উপাদান না লাগে তাদের সঙ্গে কিছু করতে. মাত্র চার ফেরৎ. এটা সবসময় একটি একক পদক্ষেপ. 

বস্তুত, 2 nums-- যোগ যা আমরা হিসাবে well-- আগে দেখা করেছি শুধু দুটি পূর্ণসংখ্যার প্রসেস. এটি একটি একক পদক্ষেপ না. এটা আসলে একটি দম্পতি পদক্ষেপ. আপনি একটি পেতে, আপনি বি পেতে, আপনি তাদের যোগ একসাথে, এবং আপনি আউটপুট ফলাফল. সুতরাং এটা 84 ধাপ. কিন্তু এটা সবসময় ধ্রুবক নির্বিশেষে A অথবা B. আপনি একটি পেতে আছে, বি পেতে, যোগ তাদের একসঙ্গে, আউটপুট ফলাফলের. সুতরাং যে একটি ধ্রুবক সময় অ্যালগরিদম. 

এখানে একটি একটি উদাহরণ রৈখিক সময় এলগরিদম যে সময় লাগে gets-- যে একটি অ্যালগরিদম এক অতিরিক্ত পদক্ষেপ সম্ভবত, আপনার ইনপুট 1 দ্বারা বৃদ্ধি হিসাবে. সুতরাং, আসুন আমরা খুঁজছেন বলা যাক একটি অ্যারের সংখ্যা 5 ভিতরে. আপনি একটি অবস্থা যেখানে থাকতে পারে আপনি এটা মোটামুটি তাড়াতাড়ি খুঁজে পেতে পারেন. কিন্তু আপনার কাছে থাকতে পারে একটি অবস্থা যেখানে এটা অ্যারের শেষ উপাদান হতে পারে. আকার 5 একটি অ্যারের, যদি ইন আমরা 5 নম্বর খুঁজছেন. এটা 5 পদক্ষেপ গ্রহণ করবে. এবং বাস্তবিকই, আছে যে কল্পনা এই অ্যারের মধ্যে না 5 কোথাও. আমরা এখনও আসলে তাকান আছে অ্যারের প্রতিটি উপাদান নির্ধারণ করার জন্য কিনা বা না 5 আছে. 

সুতরাং যে যা খারাপ কেস, এ উপাদান অ্যারের মধ্যে শেষ হয় বা এ সব কোন অস্তিত্ব নেই. আমরা এখনও তাকান আছে এন উপাদানের সমস্ত. এবং তাই এই অ্যালগরিদম রৈখিক সময়ে সঞ্চালিত হয়. আপনি যে নিশ্চিত করতে পারেন বলার অপেক্ষা রাখে না একটি সামান্য বিট extrapolating, আমরা একটি 6-অ্যারের উপাদান ছিল যদি ও আমরা, সংখ্যা 5 এ খুঁজছেন সেটা এটা 6 পদক্ষেপ নিতে পারে. আমরা একটি 7-উপাদান অ্যারের থাকে এবং আমরা 5 নম্বর খুঁজছেন. 7 পদক্ষেপ নিতে পারে. আমরা আরও একটি উপাদান যোগ হিসাবে আমাদের অ্যারে, এটি আরও একটি পদক্ষেপ নেয়. যে একটি রৈখিক অ্যালগরিদম খারাপ-ক্ষেত্রে. 

দম্পতি জন্য দ্রুত প্রশ্ন. কি runtime-- কী খারাপ-ক্ষেত্রে রানটাইম কোড এই বিশেষ স্নিপেট? তাই আমি যে রান এখানে একটি 4 লুপ আছে J 0, মিটার পর্যন্ত সব পথ সমান থেকে. এবং কি আমি এখানে দেখছি, যে লুপ শরীরের ধ্রুব সময় সঞ্চালিত হয়. তাই পরিভাষা যে ব্যবহার আমরা ইতিমধ্যে কি about-- সায়ীদ করেছি খারাপ-কেস হবে এই অ্যালগরিদম রানটাইম? কয়েক সেকেন্ড সময় নিন. লুপ এর ভিতরের অংশ ধ্রুব সময় সঞ্চালিত হয়. আর বাইরের অংশ লুপ এম বার চালানো যাচ্ছে. তাই খারাপ-ক্ষেত্রে রানটাইম এখানে কি? আপনি মিটার বড়-হে অনুমান করেছেন? আপনি সঠিক হতে চাই. 

কিভাবে অন্য এক সম্পর্কে? আমরা একটি আছে এই সময় একটি লুপ এর ভিতরে লুপ. আমরা একটি বাইরের লুপ আছে যে শূন্য থেকে P চালায়. আর আমরা চালানো একটি ভেতরের লুপ আছে শূন্য থেকে পি, এবং যে এর ভিতর, আমি রাষ্ট্র শরীরের যে লুপ ধ্রুব সময় সঞ্চালিত হয়. তাই খারাপ-ক্ষেত্রে রানটাইম কি কোড এই বিশেষ স্নিপেট? ওয়েল, আবার, আমরা একটি আছে P বার সঞ্চালিত হয় যে বাইরের লুপ. আর প্রতিটি সময়ের মধ্যে পুনরাবৃত্তির যে লুপ, বরং. আমরা একটি অভ্যন্তরীণ লুপ আছে যে P বার রান. যে এর ভিতরে এবং তারপর, আছে সেখানে ধ্রুব সময়ের মধ্যে সামান্য স্নিপেট. 

আমরা একটি বাইরের লুপ আছে সুতরাং যে যার ভিতর P বার রান একটি অভ্যন্তরীণ লুপ যে কি বার পুনরাবৃত্তি P রান খারাপ-ক্ষেত্রে রানটাইম এই কোড স্নিপেট? আপনি পি বড়-বর্গ হে অনুমান করেছেন? 

আমি ডগ লয়েড আছি. এটি CS50.