ldhnam
Công nghệ, kinh tế, và những suy nghĩ rời rạc.Technology, economics, and scattered thoughts.
← Cấu trúc dữ liệu & Giải thuật← Data Structures & Algorithms
Cấu trúc dữ liệu & Giải thuậtData Structures & Algorithms7 Th8, 2026Aug 7, 202615 phút đọc12 min read

Nền tảng lập trình & PseudocodeProgramming Fundamentals & Pseudocode

Mục lục
  1. Tổng quan
  2. Kiến thức nền tảng
  3. Chọn ngôn ngữ
  4. Syntax của ngôn ngữ
  5. Control structure
  6. Function
  7. OOP cơ bản
  8. Khái niệm chính
  9. Pseudocode
  10. Loop invariant — làm sao biết một thuật toán là đúng
  11. Tracing — kỹ thuật debug không tốn gì
  12. Mô hình RAM — “một bước” nghĩa là gì
  13. Best Practices
  14. Tài liệu tham khảo
Table of contents
  1. Overview
  2. Fundamentals
  3. Picking a language
  4. Language syntax
  5. Control structures
  6. Functions
  7. OOP basics
  8. Key Concepts
  9. Pseudocode
  10. Loop invariants — how to know an algorithm is correct
  11. Tracing — the debugging technique that costs nothing
  12. The RAM model — what “one step” means
  13. Best Practices
  14. References

Thuộc bộ kiến thức Data Structures & Algorithms Roadmap.

Tổng quan

Data structures và algorithms không phải là một ngôn ngữ lập trình. Chúng là cách tư duy về việc dữ liệu được bố trí trong memory ra sao và một chuỗi các bước biến đổi dữ liệu đó như thế nào — và cách tư duy này mang đi đâu cũng dùng được. Binary search vẫn là cùng một ý tưởng trong Python, Go, Java hay C++; chỉ có syntax bao quanh nó là thay đổi. Đó là lý do roadmap mở đầu bằng “Pick a Language” chứ không phải “Learn C++”: ngôn ngữ là phương tiện, không phải đích đến.

Dù vậy, bạn không thể học algorithms trong chân không. Trước khi lập luận được rằng một lần lookup trên hash table có phải là O(1) hay không, bạn cần thành thạo một ngôn ngữ nào đó đến mức viết một vòng lặp, một function hay một class không tốn chút suy nghĩ nào. Nếu bạn vẫn còn vật lộn với syntax thì thuật toán nào trông cũng khó, bởi bạn không phân biệt được phần khó nào đến từ thuật toán và phần nào đến từ ngôn ngữ. Những kiến thức nền tảng dưới đây — biến, control structure, function, OOP cơ bản — là cái giá vé vào cửa.

Nửa còn lại của chủ đề này là pseudocode: cách mô tả thuật toán bằng ngôn ngữ tự nhiên, dành cho con người đọc chứ không phải cho máy chạy. Pseudocode là cách thuật toán được truyền đạt trong sách giáo khoa, paper, phỏng vấn và các buổi thảo luận thiết kế, chính bởi vì nó lược bỏ hết nhiễu đặc thù của từng ngôn ngữ và chỉ để lại tư duy thuật toán. Đọc được pseudocode giúp bạn học từ bất kỳ nguồn nào; viết được pseudocode giúp bạn nghĩ xong thuật toán trước khi cam kết vào một implementation cụ thể.

Xuyên suốt bộ kiến thức này, phần implementation được viết bằng Python, được chọn vì trong các ngôn ngữ phổ thông thì nó đọc gần với pseudocode nhất — không khai báo kiểu, không dấu ngoặc nhọn, không quản lý memory thủ công làm phân tán khỏi thuật toán. Ở những chỗ mà tiện ích cấp cao của Python sẽ che mất cơ chế đang được dạy (list của nó vốn đã là dynamic array, dict của nó vốn đã là hash table), ghi chú sẽ tự xây dựng lại cấu trúc từ đầu thay vì dùng built-in.

Kiến thức nền tảng

Chọn ngôn ngữ

Roadmap liệt kê JavaScript, Java, Go, C#, C++, Python, Rust và Ruby. Ngôn ngữ nào cũng dùng được. Lời khuyên duy nhất đáng đưa ra là:

Ngôn ngữĐọc giống pseudocodeLộ ra phần máyStandard library cho DSA
PythonXuất sắcKém — mọi thứ là object, không quản lý memory thủ côngXuất sắc (heapq, collections, bisect)
JavaTạmTạm — có reference nhưng do GC quản lýXuất sắc (ArrayDeque, PriorityQueue, TreeMap)
GoTốtTốt — slice lộ ra cap/len, pointer tường minhTạm (container/heap, nhưng generics mới có gần đây)
C++KémXuất sắc — pointer, stack vs heap, lifetime thủ côngXuất sắc (STL: vector, map, priority_queue)
JavaScriptTốtKém — array thực chất là object kiểu hash bên dướiYếu (không có heap hay ordered map dựng sẵn)
RustTạmXuất sắc — ownership làm lifetime trở nên tường minhTốt (BinaryHeap, BTreeMap, VecDeque)

Syntax của ngôn ngữ

Syntax là tập quy tắc quy định chương trình phải được cấu trúc như thế nào — biến khai báo ra sao, function gọi thế nào, block được phân định bằng gì. Nó là ngữ pháp của ngôn ngữ, và làm sai sẽ sinh ra syntax error khiến chương trình dừng trước khi kịp chạy. Syntax cũng là phần ít thú vị nhất của lập trình: nó là học thuộc, nó khác nhau tùy tiện giữa các ngôn ngữ, và nó không dạy bạn gì về giải quyết vấn đề. Học một lần, học nhanh, rồi đi tiếp.

# Python: biến không cần khai báo kiểu, block được xác định bằng thụt lề
total = 0
name = "queue"
items = [3, 1, 4, 1, 5]
lookup = {"a": 1, "b": 2}

Control structure

Control structure điều khiển luồng thực thi đi qua chương trình. Có ba loại, và mọi thuật toán bạn từng viết đều được ghép lại từ chúng:

def classify(n):
    if n < 0:                  # rẽ nhánh
        return "negative"
    elif n == 0:
        return "zero"
    return "positive"

total = 0
for x in [3, 1, 4, 1, 5]:      # lặp — O(n) theo độ dài của list
    total += x

i = 0
while i * i <= 100:            # lặp với cận được tính toán — O(√n)
    i += 1

Function

Function là một block có tên thực hiện một nhiệm vụ cụ thể, cho phép bạn viết code một lần rồi tái sử dụng. Function nhận đầu vào (parameter), làm gì đó, và thường trả về đầu ra. Nó cũng là đơn vị của đệ quy, điều khiến function trở thành trung tâm của một phần lớn roadmap này — xem ./19-recursion-and-divide-and-conquer.md.

Bốn nhóm đáng gọi tên:

def binary_search(arr, target):        # user-defined
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# higher-order: sorted() nhận một function làm tham số `key`
people = [("Anh", 31), ("Bình", 25), ("Chi", 40)]
by_age = sorted(people, key=lambda p: p[1])   # lambda = anonymous function

OOP cơ bản

Lập trình hướng đối tượng tổ chức code quanh các object, mỗi object là một instance của một class. Class định nghĩa các thuộc tính (dữ liệu) và method (hành vi) mà mọi instance của nó cùng có. Bạn không cần OOP sâu để học thuật toán, nhưng cần đủ để định nghĩa được một node và một container, vì đó là cách gần như mọi cấu trúc dữ liệu không tầm thường được diễn đạt:

class Node:
    """Một phần tử của linked list: một giá trị cộng với link tới node kế tiếp."""
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def push_front(self, value):
        self.head = Node(value, self.head)
        self.size += 1

Bốn nguyên lý, tóm gọn:

Khái niệm chính

Pseudocode

Pseudocode là cách mô tả các bước của một thuật toán bằng ngôn ngữ tự nhiên, viết cho con người đọc. Nó mượn control structure và từ vựng từ các ngôn ngữ cấp cao nhưng không tuân theo syntax của riêng ngôn ngữ nào. Mục tiêu của nó là làm lộ ra tư duy thuật toán, chứ không phải chi tiết implementation.

Vì sao nó quan trọng: pseudocode là ngôn ngữ chung của tài liệu thuật toán. CLRS, các editorial competitive programming, các paper và phỏng vấn trên bảng trắng đều dùng nó. Nó cũng thực sự hữu ích như một công cụ nháp — viết thuật toán bằng pseudocode trước buộc bạn phải chốt xong logic trước khi bị phân tâm bởi chuyện cận vòng lặp nên là < hay <=.

Không có chuẩn duy nhất nào, nhưng các quy ước đủ ổn định để phiên bản nào cũng đọc được:

ALGORITHM BinarySearch(A, target)
    INPUT:  A — array of n comparable items, sorted ascending
            target — the value to find
    OUTPUT: index of target in A, or NOT_FOUND

    lo ← 0
    hi ← n − 1
    WHILE lo ≤ hi DO
        mid ← ⌊(lo + hi) / 2⌋
        IF A[mid] = target THEN
            RETURN mid
        ELSE IF A[mid] < target THEN
            lo ← mid + 1
        ELSE
            hi ← mid − 1
        END IF
    END WHILE
    RETURN NOT_FOUND

Các quy ước phổ biến: ← cho phép gán (tránh nhập nhằng giữa = và ==), ⌊ ⌋ cho phép chia lấy phần nguyên, thụt lề để thể hiện cấu trúc block, từ khóa viết hoa toàn bộ, và một hợp đồng INPUT/OUTPUT tường minh ở đầu. Chỉ số array trong sách giáo khoa đôi khi bắt đầu từ 1 (CLRS dùng A[1..n]) còn trong code thì bắt đầu từ 0 — luôn kiểm tra xem đang là kiểu nào, vì lỗi lệch một đơn vị giữa hai cách đánh chỉ số là nguồn bug kinh điển khi chép lại thuật toán từ sách.

Loop invariant — làm sao biết một thuật toán là đúng

Invariant là một mệnh đề đúng trước khi vòng lặp bắt đầu, vẫn đúng sau mỗi lần lặp, và — kết hợp với điều kiện thoát của vòng lặp — chứng minh thuật toán là đúng. Đây là công cụ tiêu chuẩn để lập luận về tính đúng đắn, và đáng để thấm nhuần từ sớm vì nó biến “tôi nghĩ cái này chạy đúng” thành “tôi biết cái này chạy đúng”.

Với binary search ở trên, invariant là: nếu target có mặt trong A, thì chỉ số của nó nằm trong [lo, hi].

Tracing — kỹ thuật debug không tốn gì

Trước khi chạy code, hãy chạy nó trong đầu hoặc trên giấy với một input nhỏ và ghi lại mọi biến ở mọi bước. Phần lớn bug thuật toán — sai cận vòng lặp, sai thứ tự cập nhật, một mid không bao giờ tiến lên — trở nên hiển nhiên trong một bảng trace bốn dòng, trong khi có thể ẩn mình cả tiếng đồng hồ trong debugger.

BướclohimidA[mid]so với target=7
bắt đầu06355 < 7 → lo = 4
246588 > 7 → hi = 4
34447tìm thấy → return 4

Mô hình RAM — “một bước” nghĩa là gì

Khi ta nói một thuật toán tốn O(n) bước, ta đang đếm phép toán dưới một mô hình máy được giả định. Mô hình tiêu chuẩn là RAM (Random Access Machine): memory là một array các ô, truy cập ô bất kỳ theo chỉ số tốn thời gian hằng số, và các phép toán cơ bản (số học, so sánh, gán) mỗi phép tốn một đơn vị thời gian bất kể giá trị lớn nhỏ ra sao.

Mô hình này là một lời nói dối hữu ích. Máy thật có cache, nên truy cập memory tuần tự có thể nhanh hơn cả một bậc so với truy cập ngẫu nhiên, dù mô hình RAM gọi cả hai là O(1). Máy thật có word size hữu hạn, nên nhân hai số nguyên khổng lồ không phải là một bước. Mô hình này vẫn là mặc định đúng đắn — nó làm việc phân tích trở nên khả thi và dự đoán của nó thường chính xác — nhưng biết chỗ nó vỡ sẽ giải thích được vì sao một thuật toán O(n log n) đôi khi thua một thuật toán O(n²) trên input nhỏ và thân thiện với cache. Điều này được triển khai sâu hơn trong ./03-algorithmic-complexity.md và ./04-arrays.md.

Best Practices

Tài liệu tham khảo

Part of the Data Structures & Algorithms Roadmap knowledge base.

Overview

Data structures and algorithms are not a programming language. They are a way of thinking about how data is laid out in memory and how a sequence of steps transforms it — and that thinking is portable. A binary search is the same idea in Python, Go, Java, and C++; only the syntax around it changes. This is why the roadmap opens with “Pick a Language” rather than “Learn C++”: the language is a vehicle, not the destination.

That said, you cannot study algorithms in a vacuum. Before you can reason about whether a hash table lookup is O(1), you need to be fluent enough in some language that writing a loop, a function, or a class costs you no thought at all. If you are still fighting the syntax, every algorithm looks hard, because you cannot tell which part of the difficulty comes from the algorithm and which part comes from the language. The fundamentals below — variables, control structures, functions, basic OOP — are the price of admission.

The other half of this topic is pseudocode: the plain-language description of an algorithm that is intended for humans to read, not machines to run. Pseudocode is how algorithms are communicated in textbooks, papers, interviews, and design discussions, precisely because it strips away the language-specific noise and leaves only the algorithmic thinking. Being able to read pseudocode lets you learn from any source; being able to write it lets you work out an algorithm before you commit to an implementation.

Throughout this knowledge base the implementations are written in Python, chosen because it reads closest to pseudocode of any mainstream language — there are no type declarations, no braces, and no memory management to distract from the algorithm. Where Python’s own high-level conveniences would hide the mechanics being taught (its list is already a dynamic array, its dict is already a hash table), the note builds the structure from scratch instead of using the built-in.

Fundamentals

Picking a language

The roadmap lists JavaScript, Java, Go, C#, C++, Python, Rust, and Ruby. Any of them will work. The only advice worth giving is:

LanguageReads like pseudocodeShows the machineStandard library for DSA
PythonExcellentPoor — everything is an object, no manual memoryExcellent (heapq, collections, bisect)
JavaFairFair — references but GC-managedExcellent (ArrayDeque, PriorityQueue, TreeMap)
GoGoodGood — slices expose cap/len, explicit pointersFair (container/heap, but generics are recent)
C++PoorExcellent — pointers, stack vs heap, manual lifetimeExcellent (STL: vector, map, priority_queue)
JavaScriptGoodPoor — arrays are hash-like objects under the hoodWeak (no built-in heap or ordered map)
RustFairExcellent — ownership makes lifetimes explicitGood (BinaryHeap, BTreeMap, VecDeque)

Language syntax

Syntax is the set of rules that dictate how a program must be structured — how variables are declared, how functions are called, how blocks are delimited. It is the grammar of the language, and getting it wrong produces a syntax error that stops the program before it runs. Syntax is also the least interesting part of programming: it is memorization, it varies arbitrarily between languages, and it teaches you nothing about problem solving. Learn it once, quickly, and move on.

# Python: variables need no type declaration, blocks are defined by indentation
total = 0
name = "queue"
items = [3, 1, 4, 1, 5]
lookup = {"a": 1, "b": 2}

Control structures

Control structures direct the flow of execution through a program. There are three kinds, and every algorithm you will ever write is built from them:

def classify(n):
    if n < 0:                  # selection
        return "negative"
    elif n == 0:
        return "zero"
    return "positive"

total = 0
for x in [3, 1, 4, 1, 5]:      # iteration — O(n) in the length of the list
    total += x

i = 0
while i * i <= 100:            # iteration with a computed bound — O(√n)
    i += 1

Functions

A function is a named block that performs a specific task, letting you write code once and reuse it. Functions take input (parameters), do something, and usually return output. They are also the unit of recursion, which makes them central to a large part of this roadmap — see ./19-recursion-and-divide-and-conquer.md.

The four categories worth naming:

def binary_search(arr, target):        # user-defined
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# higher-order: sorted() takes a function as its `key` argument
people = [("Anh", 31), ("Bình", 25), ("Chi", 40)]
by_age = sorted(people, key=lambda p: p[1])   # lambda = anonymous function

OOP basics

Object-oriented programming organizes code around objects, each an instance of a class. A class defines the attributes (data) and methods (behaviour) shared by all its instances. You do not need deep OOP to study algorithms, but you need enough to define a node and a container, because that is how nearly every non-trivial data structure is expressed:

class Node:
    """One element of a linked list: a value plus a link to the next node."""
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def push_front(self, value):
        self.head = Node(value, self.head)
        self.size += 1

The four principles, briefly:

Key Concepts

Pseudocode

Pseudocode is a plain-language description of the steps in an algorithm, written for human reading. It borrows control structures and vocabulary from high-level languages without adhering to any one language’s syntax. Its aim is to expose the algorithmic thinking, not the implementation details.

Why it matters: pseudocode is the lingua franca of algorithm literature. CLRS, competitive programming editorials, papers, and whiteboard interviews are all conducted in it. It is also genuinely useful as a drafting tool — writing an algorithm in pseudocode first forces you to settle the logic before you get distracted by whether the loop bound should be < or <=.

There is no single standard, but conventions are stable enough that any version is readable:

ALGORITHM BinarySearch(A, target)
    INPUT:  A — array of n comparable items, sorted ascending
            target — the value to find
    OUTPUT: index of target in A, or NOT_FOUND

    lo ← 0
    hi ← n − 1
    WHILE lo ≤ hi DO
        mid ← ⌊(lo + hi) / 2⌋
        IF A[mid] = target THEN
            RETURN mid
        ELSE IF A[mid] < target THEN
            lo ← mid + 1
        ELSE
            hi ← mid − 1
        END IF
    END WHILE
    RETURN NOT_FOUND

Common conventions: ← for assignment (avoiding the = versus == ambiguity), ⌊ ⌋ for integer floor division, indentation for block structure, all-caps keywords, and an explicit INPUT/OUTPUT contract at the top. Array indexing is sometimes 1-based in textbooks (CLRS uses A[1..n]) and 0-based in code — always check which, because off-by-one errors between the two are a classic source of bugs when transcribing an algorithm from a book.

Loop invariants — how to know an algorithm is correct

An invariant is a statement that is true before the loop starts, stays true after each iteration, and — combined with the loop’s exit condition — proves the algorithm correct. This is the standard tool for reasoning about correctness, and it is worth internalizing early because it turns “I think this works” into “I know this works.”

For the binary search above, the invariant is: if target is in A at all, its index lies in [lo, hi].

Tracing — the debugging technique that costs nothing

Before running code, run it in your head or on paper with a small input and write down every variable at every step. Most algorithm bugs — wrong loop bound, wrong update order, a mid that never advances — become obvious in a four-row trace and can stay hidden for an hour in a debugger.

SteplohimidA[mid]vs target=7
start06355 < 7 → lo = 4
246588 > 7 → hi = 4
34447found → return 4

The RAM model — what “one step” means

When we say an algorithm takes O(n) steps, we are counting operations under an assumed machine model. The standard one is the RAM (Random Access Machine) model: memory is an array of cells, accessing any cell by index takes constant time, and basic operations (arithmetic, comparison, assignment) each take one unit of time regardless of the values involved.

This model is a useful lie. Real machines have caches, so accessing memory sequentially can be an order of magnitude faster than accessing it randomly, even though the RAM model calls both O(1). Real machines have finite word sizes, so multiplying two huge integers is not one step. The model is still the right default — it makes analysis tractable and its predictions are usually right — but knowing where it breaks explains why an O(n log n) algorithm sometimes loses to an O(n²) one on small, cache-friendly inputs. This is developed further in ./03-algorithmic-complexity.md and ./04-arrays.md.

Best Practices

References

Ghi chú liên quanRelated notes